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?

Show Tags

Have you met this question in a real interview? Yes  No

Discuss

SOLUTION 1:

递归解法

1 public List
      
        postorderTraversal1(TreeNode root) { 2         List
       
         ret = new ArrayList
        
         (); 3         dfs(root, ret); 4         return ret; 5     } 6      7     // Solution 1: rec 8     public void dfs(TreeNode root, List
         
           ret) { 9         if (root == null) {10             return;11         }12         13         dfs(root.left, ret);14         dfs(root.right, ret);15         ret.add(root.val);16     }
         
        
       
      

 

SOLUTION 2:

/**

     *  后序遍历迭代解法

     *  http://www.youtube.com/watch?v=hv-mJUs5mvU

     *  http://blog.csdn.net/tang_jin2015/article/details/8545457

     *  从左到右的后序 与从右到左的前序的逆序是一样的，所以就简单喽！ 哈哈

     *  用另外一个栈进行翻转即可喽

     */

1 // Solution 2: iterator 2     public List
      
        postorderTraversal(TreeNode root) { 3         List
       
         ret = new ArrayList
        
         (); 4         if (root == null) { 5             return ret; 6         } 7          8         Stack
         
           s = new Stack
          
           (); 9         Stack
           
             out = new Stack
            
             ();10 11 s.push(root);12 13 while (!s.isEmpty()) {14 TreeNode cur = s.pop();15 out.push(cur.val);16 17 if (cur.left != null) {18 s.push(cur.left);19 }20 21 if (cur.right != null) {22 s.push(cur.right);23 }24 }25 26 while (!out.isEmpty()) {27 ret.add(out.pop());28 }29 30 return ret;31 }
            
           
          
         
        
       
      

 

GITHUB: