94. 二叉树的中序遍历

题目

94. 二叉树的中序遍历（简单）

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

示例 1：

输入：

[1,null,2,3]

输出：

[1,3,2]

示例 2：

输入：

[]

输出：

[]

示例 3：

输入：

[1]

输出：

[1]

提示：

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

思路

中序遍历 = 左子树 → 根 → 右子树。写法一用递归；写法二用颜色标记法把递归压进显式栈：白色节点表示尚未访问（按右、根、左的顺序重新入栈），灰色节点表示可以输出。

代码

方法一：递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        dfs(root)
        return res

方法二：迭代（颜色标记法）

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