Java二叉树后序遍历：递归与迭代

二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

如下便是一棵二叉树：

二叉树的后序遍历方式为：

1. 如果根节点有左子树，遍历左子树

2. 如果根节点有右子树，遍历右子树

3. 遍历根节点

注意，上述步骤1、2同样以1、2、3的顺序进行遍历。

后序遍历方式1：迭代

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> order = new ArrayList<Integer>();
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        // 指向上一个被访问的节点
        TreeNode pre = null;
        while(root!=null || !stack.isEmpty()){
            // 遍历到左下
            while(root!=null){
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            if(root.right==null || root.right == pre){
                order.add(root.val);
                pre = root;
                // 保证了不会再次遍历已经遍历过的左子树
                root = null;
            }else{
                stack.push(root);
                root = root.right;
            }
        }
        return order;
}

后序遍历方式2：递归

public void postorder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 遍历左子树
    postorder(root.left, res);
    // 遍历右子树
    postorder(root.right, res);
    // 遍历根节点
    order.add(root.val);
}

二叉树的前序遍历（递归与迭代的实现）