题解 |【通俗易懂】 #二叉树的中序遍历#颜色标记这个好

已默认你已经读懂题意

在树的深度优先遍历里面（包括前序、中序、后序这三种遍历），做二叉树的中序遍历其实递归方法是最为直观易懂，但是考虑到效率的问题，我的建议不使用递归。

另外就是栈迭代的方法虽然确实提高了效率，但嵌套循环太多导致非常的烧脑，不易理解，容易造成“一看就懂，一写就废”的尴尬，另外对于其他不同的遍历顺序（如前序、中序、后序），循环结构差异很大，不能做到代码的复用。

所以，这个咋办啊

做过遗传学大题没有？

还是熟悉的味道

“母患，子必患...”

收

都扯到外婆家去了，可以用一种“颜色标记法”（瞎起的名字……），这种方法的好处兼具栈迭代方法的高效，又能像递归方法一样简洁容易懂，更重要的是，这种方法对于前序、中序、或者后序遍历，都能够写出完全一致的代码,符合真香定律。

我的解题思路如下

用颜色标记节点的状态，新的结点标记成白色，已经访问过的结点标记成灰色；那么就有两种情况，如果遇到的是白色结点，下一步把它变成灰色结点，然后把该结点的右边的子节点、自身、左边的子节点依次入栈；如果你遇到的是灰色结点，则把节点的值进行输出。

使用这种方法实现的中序遍历代码如下

//python这么来写
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