LeetCode 145. Binary Tree Postorder Traversal

Problem

LeetCode 145. Binary Tree Postorder Traversal

1. 题目简述

给出一颗二叉树，返回其后序遍历的顺序（List形式），且尽量使用非递归的形式。例如：

Input: [1,null,2,3]
1
 \
  2
 /
3
Output: [3,2,1]  

2. 算法思路

Stack：

递归的形式很好写，普通的后序遍历，这里不再赘述。问题在于非递归（迭代）的形式怎么办。

后序遍历应该是三种遍历中最难的一种了，为什么呢？问题在于我们很难界定什么时候去访问节点，什么时候去压栈。我们访问的顺序应该是“左->右->中”，也就是说我们压栈的顺序是“中->右->左”。

以上面为例，如果当前节点node为2节点，我们如何判断接下来是将3节点push下去还是访问2节点然后跳出呢？这里用一个lastNode变量来判断上次访问是否是当前节点的孩子节点。

遍历过程：

1. 将根节点压栈；
2. 如果栈不为空，则循环：pop栈顶元素给node，如果当前节点为叶子节点或者当前节点是lastNode的父节点，则访问该节点的值；如果都不满足，则说明当前节点的孩子还没被压栈，按照“中->右->左”的顺序压栈。
3. 栈为空，循环终了

3. 解法

1. 遍历时，注意lastNode的赋值

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        TreeNode node = root, lastNode = root;
        stack.push(node);

        while (!stack.isEmpty() && node != null) {
            node = stack.pop();
            if ((node.left == null && node.right == null) || node.left == lastNode || node.right == lastNode) {
                // node为叶子节点或者访问返回到当前节点
                list.add(node.val);
                lastNode = node;
            } else {
                // 栈还没压到叶子节点
                stack.push(node);
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }

        return list;
    }
}