【常见面试算法】非递归遍历二叉树

问题

递归遍历二叉树很简单，遵循前序中左右，中序左中右，后续左右中的顺序即可。
但是使用迭代遍历二叉树，我们需要自己使用栈来保存信息。
记住，递归能解决的问题，使用迭代也都可以解决，遍历二叉树、归并排序都是这样。

前序遍历

使用栈保存节点信息，每次循环，先把当前节点也就是根节点的值打印出来（加入list），再向栈中push右节点和左节点，直到栈空。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            //因为使用的是栈，记得先push右边，再push左边
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }

        }
        return list;
    }
}

中序遍历

迭代中序遍历二叉树要稍微麻烦些，但显然也要利用栈，步骤如下：

1. 将当前节点cur的左边界全部push进栈，即不停地cur = cur.left；
2. 当cur为null，此时从栈中pop一个节点node，打印出它的值（加入list），并让cur = node.right，重复步骤1；
3. 当stack为空且cur为空，循环结束。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;

        Stack<TreeNode> stack = new Stack<>();

        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode node = stack.pop();
                list.add(node.val);
                root = node.right;
            }
        }
        return list;
    }
}

后序遍历

后序遍历和前序遍历一模一样，只是左右子节点压栈顺序反过来，此外将结果放入list时需要注意每次都插入第0个位置，否则结果是反的。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            //在0处插入节点值。
            list.add(0,node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        return list;
    }
}