[LeetCode]: 145: Binary Tree Postorder Traversal

题目：

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：递归解决

 

代码：

    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> arrResult = new ArrayList<Integer>();
        return AddNode(root,arrResult);
    }
    
    public ArrayList<Integer> AddNode(TreeNode root,ArrayList<Integer> arrTotal) {
        if(root == null){
            return arrTotal;
        }

        AddNode(root.left , arrTotal);
        AddNode(root.right , arrTotal);
        arrTotal.add(root.val);
        return arrTotal;
    }

 

思路2：广度优先搜索的变形，采用栈来记录节点

其中关键的一个点就是：当某一个节点的左子树或右子树不为空的时候，

     - 需要将左子树或者右子树也加到这个栈里面

     - 同时还要将原节点对应的左右子树置成null，这样再次遍历栈时，再回到那个节点才不会引起无限循环

    public ArrayList<Integer> postorderTraversal(TreeNode root) {

        ArrayList<Integer> arrResult = new ArrayList<Integer>();
        Stack<TreeNode> staTemp = new Stack<TreeNode>();
        Stack<TreeNode> staResult= new Stack<TreeNode>();
        
        if(root == null){
            return arrResult;
        }

        staTemp.push(root);
        while(!staTemp.empty()){
            TreeNode nodeTemp = staTemp.peek();
            
            if(nodeTemp.left == null && nodeTemp.right == null){
                arrResult.add(nodeTemp.val);
                staTemp.pop();
            }
            else{
                if(nodeTemp.right != null){
                    staTemp.push(nodeTemp.right);
                    nodeTemp.right = null;
                }
                
                if(nodeTemp.left != null){
                    staTemp.push(nodeTemp.left);
                    nodeTemp.left = null;
                }
            }
            
        }
        
        
        return arrResult;
    }