二叉树的后序非递归遍历（巧妙思想）

大家都知道二叉树的前序非递归遍历非常好写：

//二叉树的结构
public class TreeNode {
    TreeNode left;
    TreeNode right;
    int val;

    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

首先判断根是否为空，将根节点入栈

1.若栈为空，则退出循环 
2.将栈顶元素弹出，访问弹出的节点 
3.若弹出的节点的右孩子不为空则将右孩子入栈 
4.若弹出的节点的左孩子不为空则将左孩子入栈 
5.返回1

void preOrder(){
    Stack<TreeNode> stack = new Stack<TreeNode>();
    if (root != null) {
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            visit(root);
            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

而二叉树的后序非递归遍历就比较难写，因为涉及到判断节点的访问状态…

现在有个很巧妙的方法：

前序：根->左->右 
后序：左->右->根

那么可以把后序当作：根->右->左，然后再反转一下即可。

ArrayList<Integer> postOrder(TreeNode root) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    if (root != null) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        //反转
        Collections.reverse(list);
    }
    return list;
}