题目

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

题解

https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/25220/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/

官方题解中介绍了三种方法来完成树的中序遍历，包括：

  • 递归
  • 借助栈的迭代方法
  • 莫里斯遍历

在树的深度优先遍历中（包括前序、中序、后序遍历），递归方法最为直观易懂，但考虑到效率，我们通常不推荐使用递归。

栈迭代方法虽然提高了效率，但其嵌套循环却非常烧脑，不易理解，容易造成 “一看就懂，一写就废” 的窘况。而且对于不同的遍历顺序（前序、中序、后序），循环结构差异很大，更增加了记忆负担。

因此，我在这里介绍一种 “颜色标记法” （瞎起的名字……），兼具栈迭代方法的高效，又像递归方法一样简洁易懂，更重要的是，这种方法对于前序、中序、后序遍历，能够写出完全一致的代码。

其核心思想如下：

  • 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
  • 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
  • 如果遇到的节点为灰色，则将节点的值输出。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
type Color int

const (
    WHITE Color = 0
    BLACK Color = 1
)

type MarkedNode struct {
    Node *TreeNode
    Color Color
}

func inorderTraversal(root *TreeNode) []int {
    ans := []int{}
    stack := []*MarkedNode{{root, WHITE}}
    for ;len(stack) > 0; {
        cur := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if cur.Node == nil {
            continue
        }
        if cur.Color == WHITE {
            stack = append(stack, &MarkedNode{cur.Node.Right, WHITE})
            stack = append(stack, &MarkedNode{cur.Node, BLACK})
            stack = append(stack, &MarkedNode{cur.Node.Left, WHITE})
        } else {
            ans = append(ans, cur.Node.Val)
        }
    } 
    return ans
}