leetcode--06. 二叉树后序遍历

题目:
Given a binary tree, return the postorder traversal of its nodes' values.
Note: Recursive solution is trivial, could you do it iteratively?
给定一二叉树，返回节点值的后序遍历
注意：递归的解决方法很简单，你能用迭代地这样做吗？

思路：
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。
如果P不存在左孩子和右孩子，则可以直接访问它；
或者P存在孩子，但是其孩子都已被访问过了，则同样可以直接访问该结点
若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了
每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
         ArrayList<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
         
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        stack.push(root);
        while(!stack.isEmpty()){
            // 只看栈顶元素，不弹出
            TreeNode cur = stack.peek();
            if((cur.left == null && cur.right == null)
                || (pre != null && (pre == cur.left || pre == cur.right))){
                list.add(cur.val);
                stack.pop();
                pre = cur;
            }
            else{
                if(cur.right != null)
                    stack.push(cur.right);
                if(cur.left != null)
                    stack.push(cur.left);
            }
        }
        return list;
    }
}

ps:
前、中、后序遍历：

image.png
前：根 ->左 ->右
ABDECF
中：左 ->根 ->右
DBAEFC
后：左 ->右 ->根
DEBFCA