/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
  //recursive way:
  // public List<Integer> postOrder(TreeNode root) {
  //   // Write your solution here.
  //   List<Integer> result = new ArrayList<>();
  //   postOrderHelper(root, result);
  //   return result;
  // }
  // private void postOrderHelper(TreeNode root, List<Integer> result) {
  //   if (root == null) {
  //     return;
  //   }
  //   postOrderHelper(root.left, result);
  //   postOrderHelper(root.right, result);
  //   result.add(root.key);
  // }

  //iterative way:
  public List<Integer> postOrder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
      return result;
    }
    TreeNode prev = null;
    Deque<TreeNode> stack = new LinkedList<>();
    stack.offerFirst(root);
    while(!stack.isEmpty()) {
      TreeNode cur = stack.peekFirst();
      if (prev == null || cur == prev.left || cur == prev.right) {
        if (cur.left != null) {
          stack.offerFirst(cur.left);
        } else if (cur.right != null) {
          stack.offerFirst(cur.right);
        } else {
          result.add(cur.key);
          stack.pollFirst();
        }
      } else if (prev == cur.left) {
        if (cur.right != null) {
          stack.offerFirst(cur.right);
        } else {
          result.add(cur.key);
          stack.pollFirst();
        }
      } else {
        result.add(cur.key);
        stack.pollFirst();
      }
      prev = cur;
    }
    return result;
  }
}

use a prev to track where the node come from.

3 cases

1: (prev == null || cur == prev.left || cur == prev.right) 意思是要么是根节点，要么是当前节点是之前来的节点的左节点或者有节点。 这种情况要继续先往左走，再往右走， 如果都为空，就可以输出。

2：(prev == cur.left) 之前节点是当前节点的左节点， 意思是从左边回来的。 这种情况， 向右走， 为空就直接输出。

3：（prev == cur.right) 之前节点是当前节点的右节点， 意思是从右边回来的。这种情况，直接输出。

每次循环完改变prev指针，到当前节点。