二叉树后序遍历

 1  //分治
 2  public ArrayList<Integer> postorderTraversal(TreeNode root) {
 3      ArrayList<Integer> result = new ArrayList<Integer>();
 4      if(root == null) return result;
 5     
 6      ArrayList<Integer> left = postorderTraversal(root.left);
 7      ArrayList<Integer> right = postorderTraversal(root.right);
 8      result.addAll(left);
 9      result.addAll(right);
10      result.add(root.val);
11      return result;
12      
13  }
14  //非递归
15  public ArrayList<Integer> postorderTraversal(TreeNode root) {
16      ArrayList<Integer> result = new ArrayList<Integer>();
17     Stack<TreeNode> stack = new Stack<TreeNode>();
18     TreeNode prev = null; // previously traversed node
19     TreeNode curr = root;
20 
21     if (root == null) {
22         return result;
23     }
24 
25     stack.push(root);
26     while (!stack.empty()) {
27         curr = stack.peek();
28         //prev == null 也只是第一次root进来时有效，其它时候不可能为null
29         if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree
30             if (curr.left != null) {
31                 stack.push(curr.left);
32             } else if (curr.right != null) {
33                 stack.push(curr.right);
34             }
35         } else if (curr.left == prev) { // traverse up the tree from the left
36             if (curr.right != null) {
37                 stack.push(curr.right);
38             }
39         } else { // traverse up the tree from the right
40             result.add(curr.val);
41             stack.pop();
42         }
43         prev = curr;
44     }
45 
46     return result;
47  }
48  
49  //游走遍历， 要返回的结果一直作为参数在传递
50  public ArrayList<Integer> postorderTraversal(TreeNode root) {
51         ArrayList<Integer> result = new ArrayList<Integer>();
52         return    traverse(root, result);
53   }
54  private ArrayList<Integer> traverse(TreeNode root, ArrayList<Integer> result) {
55      if(root == null) return result;
56      traverse(root.left, result);
57      traverse(root.right, result);
58      result.add(root.val);
59      return result;
60  }

View Code

问题：非递归解法还是看不懂~

http://www.lintcode.com/en/problem/binary-tree-postorder-traversal/

和中序类似的非递归写法：（中序：不用维护prev，不用考虑curr 和prev的关系，直接左子完了直接弹出root，再去看右子即可。）

 1 public ArrayList<Integer> postorderTraversal(TreeNode root) {
 2        ArrayList<Integer>  result = new ArrayList<Integer> ();
 3        if(root == null) return result;
 4        Stack<TreeNode> stack = new Stack<TreeNode>();
 5        TreeNode temp = root;
 6        TreeNode prev = null;
 7        while(temp != null || !stack.empty()) {
 8            while(temp != null) {
 9                 stack.push(temp);
10                 temp = temp.left;
11            }
12            temp = stack.peek();
13            if(temp.right == null || temp .right == prev) {
14                stack.pop();
15                result.add(temp.val);
16                prev = temp;
17                temp = null;
18                
19            } else {
20                prev = temp;
21                temp = temp .right;
22            }
23            
24        }
25        return result;
26    }

View Code

注意点：

　　　　prev除了第一次root进栈之前为空，之后和curr的关系由五种情况，即：

　　　　　　pre.left == curr , pre.right == curr 是树从定向下的过程

　　　　　　curr.left == prev 　　　　　　　　　　树从左子树向上的过程

　　　　　　curr.right == prev， curr == prev　　 curr== prev说明 curr的左右子树都为null或者说curr为叶结点，而且上一个循环刚经历pre.left == curr或者pre.right 　　　　　　　　　　　　　　　　　　　　　　　　　== curr的过程，而且没有往栈里添加元素（所以才说是叶结点），所以可以添加此curr的值到result中；

　　　　　　　　　　　　　　　　　　　　　　　　　树从右子树向上的过程说明curr的左子右子都已经进栈，已经经历过右子树的prev==curr的过程，即右子树已经添加到 result中，所以可以添加此curr到result中。

　　　　　　　　　　　　　　　　　　　　　　　　　　也即这两种情况都可以添加curr到result中。

错误点：