原文链接: https://leetcode-cn.com/problems/binary-tree-inorder-traversal

英文原文

Given the root of a binary tree, return the inorder traversal of its nodes' values.

 

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [2,1]

Example 5:

Input: root = [1,null,2]
Output: [1,2]

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

Follow up: Recursive solution is trivial, could you do it iteratively?

中文题目

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

 

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

 

提示：

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

 

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

通过代码

高赞题解

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

• 递归

• 借助栈的迭代方法

• 莫里斯遍历

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

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

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

其核心思想如下：

• 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。

• 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。

• 如果遇到的节点为灰色，则将节点的值输出。

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

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

如要实现前序、后序遍历，只需要调整左右子节点的入栈顺序即可。

统计信息

通过次数	提交次数	AC比率
620764	821616	75.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
验证二叉搜索树	中等
二叉树的前序遍历	简单
二叉树的后序遍历	简单
二叉搜索树迭代器	中等
二叉搜索树中第K小的元素	中等
最接近的二叉搜索树值 II	困难
二叉搜索树中的中序后继	中等
将二叉搜索树转化为排序的双向链表	中等
二叉搜索树节点最小距离	简单