Lexi's Leetcode solutions

用两个stack O(n)的方法：

1. 一个stack s1 push root。
2. 一边pop s1进s2，一边把pop的left, right push进s1（先左后右，这先进s2的是右边，左边在s2靠前部分，所以最后先print出来）
3. 这样最后s2就是一个正好从上到下是post order的traversal，一边pop一边print就行了。

public void postOrderTwoStacks(TreeNode root) {
  Stack<TreeNode> s1 = new Stack<TreeNode>();
  Stack<TreeNode> s2 = new Stack<TreeNode>();
  s1.push(root);
  while (!s1.isEmpty()) {
    TreeNode pop = s1.pop();
    s2.push(pop);
    if (pop.left != null)
      s1.push(pop.left);
    if (pop.right != null)
      s1.push(pop.right);
  }
  while (!s2.isEmpty()) {
    System.out.print(s2.pop().val + ", ");
  }
}

用一个stack O(h)的方法：

1. 一个stack，先push root
2. keep一个prev variable表示刚才试过的node（在stack里尝试来着，不管最后是否把它pop出去了），一直在更新。
3. stack.peek() == curr，每次用curr和prev比较
   • 如果prev是空或者prev是curr的parent，说明在top down的traverse，这时候可不能print prev（那就变成preorder了）；而应该push curr的左子，木有才push右子，全都木有说明curr是leaf，就pop print就行了。
   • 如果prev是curr的左子，说明在从左下角往上traverse，这时若curr有右子，则push右子（应该traverse右子）- prev应该是已经pop出来的了。
   • 如果prev是curr的右子，说明从右下角往左上traverse，这时直接pop print curr就行了，因为这时root也该出来了。

public void postOrder(TreeNode root) {
  Stack<TreeNode> s = new Stack<TreeNode>();
  s.push(root);
  TreeNode prev = null;
  while (!s.isEmpty()) {
    TreeNode curr = s.peek();
    if (prev == null || prev.left == curr || prev.right == curr) { // top down
      if (curr.left != null)
        s.push(curr.left);
      else if (curr.right != null)
        s.push(curr.right);
      else {// is leaf
        popAndPrint(s, curr);
      }
    } else if (prev == curr.left) { // from left child to parent
      if (curr.right != null)
        s.push(curr.right);
      else {
        popAndPrint(s, curr);
      }
    } else { // prev.right == curr, from right child to parent
      popAndPrint(s, curr);
    }
    prev = curr;
  }
}

private void popAndPrint(Stack<TreeNode> s, TreeNode curr) {
  System.out.print(curr.val + ", ");
  s.pop();
}