94. Binary Tree Inorder Traversa

中序遍历定义：

先访问 left subtree，再访问curNode，再访问right subtree

思路：

根据中序遍历的定义，利用stack来实现

1. 找到先要访问的left most node
2. 访问
3. 如果有right subtree，利用同样的方法，再进行访问
4. 如果没有right subtree，说明当前curNode已经被fully visited
5. 重复直到所有节点被访问

关键：

1. stack的意义是？
   既然stack的方法可以替代recursion的方法，那么stack一定实现了recursion中的某个功能。什么功能呢？backtrack！

试想一下，当访问完左子树之后需要父节点，那么怎么才能够从左子树的最后一个被访问节点跳到父节点？

利用Stack，可以先将父节点压到栈底，当左子树的节点被完全访问之后，说明栈中已无左子树的节点，栈顶节点即为父节点。

因此，stack中节点的的意义是：

• 栈顶的节点是下一个要访问的节点
• 位于顶端的比位于底端的节点先得到访问
• 已访问的节点已出栈
• 后访问的节点可能在栈中或者还未被加到栈中

2. 如何“重复直到所有节点被访问”？
   既然知道了stack的意义，那么当stack为空，则表示所有节点被访问。

while (!stack.empty()) {
  ...
}

3. 如何“找到left most node”并同时将父节点压到栈中？

while (cur.left != null) {
       stack.push(cur.left);
       cur = cur.left;
}
//add leftmost
cur = stack.pop();
rst.add(cur.val);

4. 如果有right subtree？

      // right subtree if possible
      if (cur.right != null) { 
        stack.push(cur.right);
      } 

5. 如果没有right subtree？

说明栈顶node的left subtree已经被fully visited，此时栈顶节点则为下一个要访问的点，此时可以直接回到while的起始重复执行。

但是有一个问题，当回到栈顶的节点时，又要经过3的循环，即有可能重复访问已经访问过的left subtree

解决方法是：

1. 剪枝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
      }

但改方法更改了输入，不好。

2. 既然查是否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);

3. 巧妙利用在最后使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;
  }