Leetcode 二叉树的中序遍历 -- Python实现三种解法

0 题目描述

Leetcode原题链接：二叉树的中序遍历

# 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

1 递归算法

思路与算法 首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。 定义 inorder(root) 表示当前遍历到 root节点的答案，那么按照定义，我们只要递归调用 inorder(root.left) 来遍历root 节点的左子树，然后将root 节点的值加入答案，再递归调用inorder(root.right) 来遍历 root节点的右子树即可，递归终止的条件为碰到空节点。

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: if not root: return [] return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

算法复杂度 时间复杂度：$O(n)$，其中 $n$ 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。 空间复杂度：$O(n)$。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 $O(n)$的级别。

2 迭代算法（堆栈）

递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来。

# 其核心思想如下： # 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。 # 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。 # 如果遇到的节点为灰色，则将节点的值输出。 class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: White, Gray = 0, 1 res = [] stack = [(White,root)] while stack: color, node = stack.pop() if not node: 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

算法复杂度 时间复杂度：$O(n)$，其中 $n$ 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。 空间复杂度：$O(n)$。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 $O(n)$的级别。

3 Morris 中序遍历

思路与算法 Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)。 Morris 遍历是一种常数空间的遍历方法，其本质是线索二叉树（Threaded Binary Tree), 本质上其实就是利用二叉树中 n+1 个指向NULL的指针。 Morris 遍历在遍历的过程中，通过利用叶子节点空的right指针，指向中序遍历的后继节点，从而避免了对 stack 的依赖。

# （1）对于一个节点cur，找到它左子树的最右节点，看这个节点的right指针是null还是指向cur。 # （2）如果是null，说明左子树还没处理过，更新该指针为cur，然后进入左子树继续上述流程。 # （3）如果该指针已经是cur了，说明左子树已经处理完毕，现在是处理完毕后顺这最右节点的right指针回到该cur节点的，需先将该right指针恢复为null，处理该cur节点后进入右子树重复流程⑴。 class Solution: def inorderTraversal(self, root: TreeNode) -> list: node, res = root, [] while node: if not node.left: res.append(node.val) node = node.right else: pre = node.left while pre.right and pre.right != node: pre = pre.right if not pre.right: pre.right = node node = node.left else: pre.right = None res.append(node.val) node = node.right return res

算法复杂度 时间复杂度：$O(n)$，其中 $n$ 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 $O(2n)$=$O(n)$。 空间复杂度：$O(1)$。

参考

颜色标记法-一种通用且简明的树遍历方法 莫里斯遍历