题目：

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
     
       postorderTraversal(TreeNode root) {        ArrayList
      
        arrResult = new ArrayList
       
        ();        return AddNode(root,arrResult);    }        public ArrayList
        
          AddNode(TreeNode root,ArrayList
         
           arrTotal) {        if(root == null){            return arrTotal;        }        AddNode(root.left , arrTotal);        AddNode(root.right , arrTotal);        arrTotal.add(root.val);        return arrTotal;    }
         
        
       
      
     

 

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

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

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

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

public ArrayList
     
       postorderTraversal(TreeNode root) {        ArrayList
      
        arrResult = new ArrayList
       
        ();        Stack
        
          staTemp = new Stack
         
          ();        Stack
          
            staResult= new Stack
           
            (); 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; }