文章目录

• 1. 二叉树的前序遍历
• 2. 二叉树的中序遍历（简单）
• 3. 二叉树的后序遍历

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

1. 二叉树的前序遍历

地址: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
2021/12/10
方法一： 递归
做题反思：

方法二： 迭代
做题反思：

2. 二叉树的中序遍历（简单）

地址: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
2021/12/15
方法一： 递归
做题反思：List 是一个接口， 创建对象时用他的实现类 -> ArrayList 或者 LinkedList
二叉树经典递归框架
labuladong 回溯算法思路

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
       traverse(root);
       return inorder;
    }
    List<Integer> inorder = new ArrayList<>();
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(root.left);
        inorder.add(root.val);
        traverse(root.right);
    }
}

class Solution {
    List<Integer> inorder = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        inorderTraversal(root.left);
        inorder.add(root.val);
        inorderTraversal(root.right);
        return inorder;
    }
}

方法二： 迭代
做题反思：

class Solution {
    Stack<TreeNode> stk = new Stack<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        TreeNode visited = new TreeNode(-1);
        List<Integer> inorder = new ArrayList<>();
        pushLeftBatch(root);

        while (!stk.isEmpty()) {
            TreeNode p = stk.peek();
            if ((p.left == null || p.left == visited)
                && p.right != visited) {
                inorder.add(p.val);
                pushLeftBatch(p.right);
            }
            if (p.right == null || p.right == visited) {
                visited = stk.pop();
            }
        }

        return inorder;
    }

    void pushLeftBatch(TreeNode root) {
        while (root != null) {
            stk.push(root);
            root = root.left;
        }
    }
}

方法三：labuladong 动态规划思路

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        list.addAll(inorderTraversal(root.left));
        list.add(root.val);
        list.addAll(inorderTraversal(root.right));
        return list;
    }
}

3. 二叉树的后序遍历

地址: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
2021/12/10
方法一： 递归
做题反思：

方法二： 迭代
做题反思：

1. stack.peek()
   参数：该方法不带任何参数。
   返回值：该方法返回栈顶元素，如果栈为空则返回NULL。

2. stack.pop()
   参数：该方法不带任何参数。
   返回值：此方法返回存在于堆栈顶部的元素，然后将其删除。

3. stack.push( E 元素)
   参数：该方法接受一个Stack 类型的参数元素，并引用要压入堆栈的元素。
   返回值：该方法返回传递的参数。

任何一个二叉树的算法，如果你想把递归改成迭代，都可以套用这个框架，只要把递归的前中后序位置的代码对应过来就行了。

迭代解法到这里就搞定了，不过我还是想强调，除了 BFS 层级遍历之外，二叉树的题目还是用递归的方式来做，因为递归是最符合二叉树结构特点的。

说到底，这个迭代解法就是在用栈模拟递归调用，所以对照着递归解法，应该不难理解和记忆。

理论上，所有递归算法都可以利用栈改成迭代的形式，因为计算机本质上就是借助栈来迭代地执行递归函数的。

https://labuladong.gitee.io/algo/2/18/32/