本篇讨论都是迭代写法


二叉树的前序=二叉树的dfs 比较符合人的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {

        
        Stack<TreeNode> st=new Stack<TreeNode>();
        List<Integer> result=new ArrayList<Integer>();
        if(root==null)
            return result;
        st.push(root);
        while(!st.empty()){
            TreeNode cur=st.pop();
            result.add(cur.val);
            if(cur.right!=null)
                st.push(cur.right);
            if(cur.left!=null)
                st.push(cur.left);
        }
        return result;

    }
}

中序按照符合人的思路来比较不优雅，解题思路
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/jin-hu-shuang-bai-de-die-dai-zhong-xu-by-h4ri/

这个思路有一个很好的视频讲解
https://www.bilibili.com/video/BV15k4y1R7P3
1.每次控制权移交后进入while的新一次循环：我有左孩子吗
有就交控制权给左孩子 没有就自己进res
2.1里面自己进res了 我有右孩子吗
有就控制权给右孩子 没有就还控制权

交控制权root=root.left/right 同时需要记录控制权变更stack.push(root.left/right);
还控制权root=stack.pop()

我自己的实现 试了好久才写出来 感觉思路简单 实现并不容易

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public static List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        
        //stack一开始是空的
        Stack<TreeNode> stack = new Stack<>();

        while (true) {
            //有左儿子 交控制权给左儿子 并断开左儿子 只有有左儿子的node可能会被交还控制权 需要push
            if (root.left != null) {
                stack.push(root);
                TreeNode tmp = root;
                root = root.left;
                tmp.left = null;
            }//没左
            else {
                res.add(root.val);
                //没左有右 断开右儿子 
                if (root.right != null) {
                    TreeNode tmp = root;
                    root = root.right;
                    //这里断不断无所谓
                    tmp.right = null;
                    //没左没右
                } else {
                    if (stack.empty()) {
                        break;
                    }
                    root = stack.pop();
                }
            }
        }
        return res;
    }

1.对于当前中序遍历到的某个节点，如果他左子树不空，就往左遍历，

2.当作子树为空或遍历返回到当前节点时，访问当前这个节点（操作一下），然后将当前节点的左指针制空（防止循环遍历卡住）

3.判断当前节点的右子树是否为空，不空就向右遍历，回到1，空就向上返回。

大概思路就是 如果如果左边有孩子，第一次会在if里加进去，第二次就会跳过这if了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 使用迭代 直接压栈即可
        List<Integer> res = new ArrayList<>();
        Stack <TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);

         if(root == null) //处理特殊情况
            return res;
        while(!stack.empty())
        {
            if(root.left != null) //如果当前节点的左子树不空，就向左走，压栈左儿子节点
            {
                stack.push(root.left);
                root = root.left;
            }
            else //如果当前节点的左子树空了
            {
                root = stack.pop(); //弹栈，返回上一个遍历到的节点
                
                res.add(root.val); //把他压入返回数组，此时就是中序的顺序
                root. left = null; //将左指针制空，表明当前节点的左边已经处理过了
                if(root.right != null) //判断当前节点的右子树空不空，不空就进入右遍处理
                {
                    root = root.right;
                    stack.push(root);
                }
            }
        }

        return res;


    }
}

还有一个写法 也比标准答案舒服一点。
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/shou-hua-tu-jie-yong-zhan-mo-ni-zhong-xu-bian-li-z/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const inorderTraversal = (root) => {
  const res = [];
  const stack = [];

  while (root) {        // 能压入栈的左子节点都压进来
    stack.push(root);
    root = root.left;
  }
  while (stack.length) {
    let node = stack.pop(); // 栈顶的节点出栈
    res.push(node.val);     // 在压入右子树之前，处理它的数值部分（因为中序遍历）
    node = node.right;      // 获取它的右子树
    while (node) {          // 右子树存在，执行while循环    
      stack.push(node);     // 压入当前root
      node = node.left;     // 不断压入左子节点
    }
  }
  return res;
};

不按照人的思路来写 个人感觉这个看能看懂 自己写很容易忘 没什么意思 但是这种写法可以推广到前序和后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {


          
       if (root == null) {
            return Collections.emptyList();
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> res = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode node = stack.pop();
                res.add(node.val);
                if (node.right != null) {
                    root = node.right;
                }
            }
        }
        return res;

    }
}