Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

这道题要求用非递归的方式，这里使用了stack来保存需要访问的节点，用hashmap记录已经添加到result中的节点

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.HashMap;
 4 import java.util.Hashtable;
 5 import java.util.List;
 6 import java.util.Stack;
 7 
 8 public class Solution {
 9     private List<Integer> result = new ArrayList<Integer>();
10     private HashMap<TreeNode , Integer> visited = new HashMap<TreeNode, Integer>();
11     
12     public List<Integer> postorderTraversal(TreeNode root) {
13         if(null == root)
14             return result;
15         Stack<TreeNode> stack = new Stack<TreeNode>();
16         stack.push(root);
17         while(!stack.isEmpty()){
18             root = stack.peek();                                                    //获取栈顶元素的值，但不出栈
19             if(root.left != null && visited.get(root.left) == null)
20                 while(root.left != null && visited.get(root.left) == null){                //寻找左子树,且没有被访问过
21                     root = root.left;
22                     stack.push(root);
23                 }//while
24             else if(root.right != null && visited.get(root.right) == null)
25             {
26                 root = root.right;
27                 stack.push(root);
28             }
29             
30             else{
31                 result.add(root.val);
32                 visited.put(root, 1);
33                 stack.pop();                            //出栈
34             }            
35         }
36         
37         return result;
38     }     
39 }

递归实现

 1 public class Solution {
 2     private List<Integer> result = new ArrayList<Integer>();
 3     
 4     public List<Integer> postorderTraversal(TreeNode root) {
 5         postOrder(root);        
 6         
 7         return result;
 8     }
 9     private void postOrder(TreeNode root){
10         if(root != null){
11             postorderTraversal(root.left);
12             postorderTraversal(root.right);
13             result.add(root.val);
14         }//if
15     }    
16 }