中序遍历定义：
先访问 left subtree，再访问curNode，再访问right subtree
思路：
根据中序遍历的定义，利用stack来实现
1. 找到先要访问的left most node
2. 访问
3. 如果有right subtree，利用同样的方法，再进行访问
4. 如果没有right subtree，说明当前curNode已经被fully visited
5. 重复直到所有节点被访问
关键：
- stack的意义是？
既然stack的方法可以替代recursion的方法，那么stack一定实现了recursion中的某个功能。什么功能呢？backtrack！
试想一下，当访问完左子树之后需要父节点，那么怎么才能够从左子树的最后一个被访问节点跳到父节点？
利用Stack，可以先将父节点压到栈底，当左子树的节点被完全访问之后，说明栈中已无左子树的节点，栈顶节点即为父节点。
因此，stack中节点的的意义是：
- 栈顶的节点是下一个要访问的节点
- 位于顶端的比位于底端的节点先得到访问
- 已访问的节点已出栈
- 后访问的节点可能在栈中或者还未被加到栈中
- 如何“重复直到所有节点被访问”？
既然知道了stack的意义，那么当stack为空，则表示所有节点被访问。
while (!stack.empty()) {
...
}
- 如何“找到left most node”并同时将父节点压到栈中？
while (cur.left != null) {
stack.push(cur.left);
cur = cur.left;
}
//add leftmost
cur = stack.pop();
rst.add(cur.val);
- 如果有right subtree？
// right subtree if possible
if (cur.right != null) {
stack.push(cur.right);
}
- 如果没有right subtree？
说明栈顶node的left subtree已经被fully visited，此时栈顶节点则为下一个要访问的点，此时可以直接回到while的起始重复执行。
但是有一个问题，当回到栈顶的节点时，又要经过3的循环，即有可能重复访问已经访问过的left subtree
解决方法是：
- 剪枝cut branch
因为当发现没有right subtree时，说明栈顶node的left subtree已经被fully visited，因此可以将其left设置为null。
// right subtree if possible
if (cur.right != null) {
stack.push(cur.right);
} else if (!stack.empty()) { //cur subtree is fully visited
stack.peek().left = null; //cut cur subtree
}
但改方法更改了输入，不好。
- 既然查是否visited嘛，利用个set呗
while (cur.left != null && !visited.contains(cur.left)) {
stack.push(cur.left);
cur = cur.left;
}
//add leftmost
cur = stack.pop();
rst.add(cur.val);
visited.add(cur);
- 巧妙利用在最后使curNode = curNode.right + 找leftmost之前判断一下curNode是否为null，将判断当前subtree是否被fully visited的任务放到找leftmost之前。
while (!stack.empty()) {
if (cur != null) { //when curNode == null, it means cur subtree is fully visited
// push into stack until the leftmost
while (cur.left != null) {
stack.push(cur.left);
cur = cur.left;
}
}
//add leftmost
cur = stack.pop();
rst.add(cur.val);
// right subtree if possible
if (cur.right != null) {
stack.push(cur.right);
}
cur = cur.right;
}
return rst;
}
