此方法借鉴树的遍历递归方法，结合了栈的后进先出。
利用栈展开树，每次访问根的时候（即白色从栈中pop出）把遍历顺序确定下来，就是入栈的顺序，并把根标为灰色，这样子下次从栈中弹出的顺序就是所求。每次我们访问根结点的时候顺带就把孩子放进栈里（白色），
每一轮弹出一个，灰色的表明它和孩子的顺序已经放在栈里了，就可以输出了，白色表示它和父亲的关系已经做好了，和孩子的关系还没放进栈里，所以得做一下。
在树的深度优先遍历中（包括前序、中序、后序遍历），递归方法最为直观易懂，但考虑到效率，我们通常不推荐使用递归。
栈迭代方法虽然提高了效率，但其嵌套循环却非常烧脑，不易理解，容易造成“一看就懂，一写就废”的窘况。而且对于不同的遍历顺序（前序、中序、后序），循环结构差异很大，更增加了记忆负担。
因此，我在这里介绍一种“颜色标记法”（瞎起的名字……），兼具栈迭代方法的高效，又像递归方法一样简洁易懂，更重要的是，这种方法对于前序、中序、后序遍历，能够写出完全一致的代码。
其核心思想如下：
使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。
使用这种方法实现的中序遍历如下：
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
WHITE, GRAY = 0, 1
res = []
stack = [(WHITE, root)]
while stack:
color, node = stack.pop()
if node is None: continue
if color == WHITE:
stack.append((WHITE, node.right))
stack.append((GRAY, node))
stack.append((WHITE, node.left))
else:
res.append(node.val)
return res
如要实现前序、后序遍历，只需要调整左右子节点的入栈顺序即可。
老想法
树的遍历有两种方式，递归和迭代，递归比较简单，迭代的细节需要注意。
递归
在不同位置访问节点即可。
迭代
- 用一个栈存已经接触过的节点。
- 在不同的位置访问节点。
前序：第一次接触节点就访问。入栈的时候。
中序：第二次接触。出栈的时候。
后序：第三次接触。有一个prev指针指向上一次访问的节点，会入栈两次，在第二次出栈的时候。
