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},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

链接：https://leetcode.com/problems/binary-tree-postorder-traversal/#/description

5/10/2017

算法班

还可以refactor，不过不如这个好理解

 1 public class Solution {
 2     public List<Integer> postorderTraversal(TreeNode root) {
 3         List<Integer> ret = new ArrayList<Integer>();
 4         if (root == null) return ret;
 5 
 6         Stack<TreeNode> stack = new Stack<TreeNode>();
 7         TreeNode current = root;
 8         TreeNode previous = null;
 9 
10         stack.push(current);
11 
12         while (!stack.empty()) {
13             current = stack.top();
14             if (previous == null || previous.left == current || previous.right == current) {
15                 // down
16                 if (current.left != null) {
17                     // has left, push left
18                     stack.push(current.left);
19                 } else if (current.right != null) {
20                     // no left has right, push right
21                     stack.push(current.right);
22                 } else {
23                     // no children, add to ret, pop
24                     ret.add(current.val);
25                     stack.pop();
26                 }
27             } else if (current.left == previous) {
28                 // up from left
29                 if (current.right != null) {
30                     // has right, push right
31                     stack.push(current.right);
32                 } else {
33                     // no right, add to ret, pop
34                     ret.add(current.val);
35                     stack.pop();
36                 }
37             } else {
38                 // up from right
39                 // children traversal done, add to ret, pop
40                 ret.add(current.val);
41                 stack.pop();
42             }
43             previous = current;
44         }
45         return ret;
46     }
47 }

九章官方，少了2部分的add/pop，原因是放在了下一次loop(prev == current, 落入最后一个else，再来add/pop)，但是不够明显。

上一个版本第37行是不包含prev == current的，原因是其他每一步里stack都有变化，要么pop，要么push，所以每一次Current必定有改变

九章版本里有空着的2个branch，所以第24行与上一版本的第37行是不一样的。

 1 public ArrayList<Integer> postorderTraversal(TreeNode root) {
 2     ArrayList<Integer> result = new ArrayList<Integer>();
 3     Stack<TreeNode> stack = new Stack<TreeNode>();
 4     TreeNode prev = null; // previously traversed node
 5     TreeNode curr = root;
 6 
 7     if (root == null) {
 8         return result;
 9     }
10 
11     stack.push(root);
12     while (!stack.empty()) {
13         curr = stack.peek();
14         if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree
15             if (curr.left != null) {
16                 stack.push(curr.left);
17             } else if (curr.right != null) {
18                 stack.push(curr.right);
19             }
20         } else if (curr.left == prev) { // traverse up the tree from the left
21             if (curr.right != null) {
22                 stack.push(curr.right);
23             }
24         } else { // traverse up the tree from the right
25             result.add(curr.val);
26             stack.pop();
27         }
28         prev = curr;
29     }
30 
31     return result;
32 }

别人的答案

用dequeue或者stack + reverse(cheat，我认为严格的面试管会质疑，并要求重写。。。)

https://discuss.leetcode.com/topic/30632/preorder-inorder-and-postorder-iteratively-summarization