LeetCode-二叉树的迭代遍历

题目

前序思路

1. 首先思考二叉树的前序遍历，其核心思想为:
2. 过程1：每拿到一个节点就把它保存在栈中
3. 对这个节点的左子树重复过程1，直到左子树为空。
4. 因为保存在栈中的节点都遍历了左子树但没有遍历右子树，所以对栈中节点出栈并对它的右子树重复过程1
5. 直到遍历完所有节点
6. 详细代码如下

代码

    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> ans = new ArrayList<>();
        TreeNode temp = root;
        while (temp!=null || !stack.empty()){
            //找到最左端 边找边加入ans 因为要先打印根
            while (temp!=null){
                ans.add(temp.val);
                stack.push(temp);
                temp = temp.left;
            }
            //找到这里时说明已经找到了最左端 pop出一个 找其右
            temp = stack.pop();
            temp = temp.right;
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

后序思路

1. 根据上面学到的前序遍历知识，思考后序遍历，前序遍历为根左右，后序遍历为左右根。
2. 前序遍历时，是往list尾部插的，出来的顺序是根左右，如果相反往头部插，那么出来的顺序则为右左根。
3. 那么只需先遍历到最右，再弹出并找最左，即可完成左右根的遍历。

代码

    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> ans = new ArrayList<>();
        TreeNode temp = root;
        //后序遍历为左右根
        while (!stack.empty() || temp!=null){
            while (temp!=null){
                ans.add(0,temp.val);
                stack.push(temp);
                //继续找到最左
                temp = temp.right;
            }
            temp = stack.pop();
            temp = temp.left;
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

中序思路

1. 中序思路不能完全按照前后序，因为中序为左根右，根节点并不首先或者最后打印。
2. 故修改上述代码，添加入栈的时候就不要打印了，直接入栈，其次对每个以temp为root的节点，都需要找到其最左端，所以每次循环时都要找到其最左端的节点。
3. 在找到最左端时对栈进行pop并保存结果，此时再令temp为其右节点，因为此时左中均已入栈，需要找到右节点的最左端。

代码

    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> ans = new ArrayList<>();
        TreeNode temp = root;
        //中序遍历为左根右
        while (!stack.empty() || temp!=null){
            while (temp!=null){
                stack.push(temp);
                temp = temp.left;
            }
            //弹出 并打印
            temp = stack.pop();
            ans.add(temp.val);
            temp = temp.right;
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17