其实这里iterative的写法，虽然是iterative但是还是有recursive的影子。

  1. pre: 根左右，直接反向stack添加就行了
  2. post: 左右根，因为是用addFirst从前面添加，所以stack添加的时候“左右”就行了
  3. in: 左根右，这里recursive的影子就出来了，因为左边先要遍历完才到根，所以左边一直下去都装到stack里面，然后回溯到根节点，再向右; 如果这个node没有right child, 那么直接进入下一轮while，也就是直接栈顶pop得到那个元素

Iterative inorder:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        TreeNode node = root;
        while (!st.empty() || node!=null) {
            while (node != null) {
                st.push(node);
                node = node.left;
            }
            node = st.pop(); // node is null, assign non-null node to node
            res.add(node.val);
            node = node.right;
        }
        return res;
    }
}

or easier:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) return res;
        Stack<TreeNode> st = new Stack<>();
        while (!st.empty() || root != null) {
            while (root != null) {
                st.push(root);
                root = root.left;
            }
            root = st.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}