Iterative Traversal本质是把稍后要处理的Node放到stack上，然后依逻辑不断地pop和push，直到stack为空。每次iteration，都从stack上pop出一个node，然后根据其状态采取不同的处理。理论上，每次对node的访问，可以有三种状态：from parent node, from left child and from right child。再往深入想，状态的数量其实是由print的顺序决定的。Node之所以被放入stack，是因为要在将来某时刻print，换句话说，一旦该node完成了print，它就不会再次被访问。
Pre-Order Traversal
第一次访问node，就立刻print，此后不会有第二次访问该node的可能性。所以对于pre-order，pop出来的node只有一种状态，不需要额外的flag来指示状态。
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
Deque<TreeNode> stack = new ArrayDeque();
stack.offerFirst(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollFirst();
System.out.println(node.key);
if (node.right != null) {
stack.offerFirst(node.right);
}
if (node.left != null) {
stack.offerFirst(node.left);
}
}
}
In-Order Traversal
Node在第二次访问时才会被打印，因此有两个状态：from parent node and from left child。所以，用一个boolean就可以区分两种状态。需要注意的是第二次访问时才从stack中pop，所以在进入循环时选择peek。
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.offerFirst(root);
boolean isFirstAccess = true;
while (!stack.isEmpty()) {
TreeNode curr = stack.peekFirst();
if (isFirstAccess) {
if (curr.left != null) {
stack.offerFirst(curr.left);
} else {
isFirstAccess = false;
}
} else {
System.out.println(curr.key);
stack.pollFirst();
if (curr.right != null) {
stack.offerFirst(curr.right);
isFirstAccess = true;
}
}
}
}
老师给的解法其实很有技巧性。helper为null时表示从from left child，反之则表示from parent node。我认为这种解法思路还是不太一样，这个逻辑不是stack驱动的，而是helper驱动的。可以认为helper始终是下一个从未access的node，当其为null时，就必须向上pop，直到找到右子树不为空的node。循环开始时，可以不把root放入stack。
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode helper = root;
while (helper != null || !stack.isEmpty()) {
if (helper != null) {
stack.offerFirst(helper);
helper = helper.left;
} else {
TreeNode node = stack.pollFirst();
System.out.println(node.key);
helper = node.right;
}
}
}
Post-Order Traversal
Node在第三次访问时才会打印，因此需要三种状态，所以boolean不好用了。另外，对于in-order，loop每次循环的状态其实都是可以由上一次的状态计算决定的，第二次访问某节点必然是from left child。但对于post-order，状态from parent node并不能推倒出下一个状态是from left child还是from right child。因此，用一个enum来表示状态是不行的。于是引入prev，这样就能很容易的确定当前状态了。
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.offerFirst(root);
TreeNode prev = null;
while (!stack.isEmpty()) {
TreeNode curr = stack.peekFirst();
if (prev == null || prev.left == curr || prev.right == curr) {
if (curr.left != null) {
stack.offerFirst(curr.left);
} else if (curr.right != null) {
stack.offerFirst(curr.right);
} else {
stack.pollFirst();
System.out.println(curr.key);
}
} else if (prev == curr.left) {
if (curr.right !== null) {
stack.offerFirst(curr.right);
} else {
stack.pollFirst();
System.out.println(curr.key);
}
} else {
stack.pollFirst();
System.out.println(curr.key);
}
prev = curr;
}
}
Code Carpenter 