2 binary-tree-postorder-traversa

题目描述

求给定的二叉树的后序遍历。
例如：
给定的二叉树为{1,#,2,3},
1↵ ↵ 2↵ /↵ 3↵
返回[3,2,1].
备注；用递归来解这道题太没有新意了，可以给出迭代的解法么？

Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree{1,#,2,3},
1↵ ↵ 2↵ /↵ 3↵

return[3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

示例1
输入
{1,#,2,3}
输出
[3,2,1]

代码

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

public ArrayList<Integer> postorderTraversal (TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        if(root==null)
            return arr;
        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)))
            {
                arr.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 arr;
        // write code here
    }