LeetCode | 二叉树的中序遍历
分类：二叉树 / 深度优先搜索 / 栈
题目
给定一棵二叉树的根节点 root，返回它的中序遍历结果。
中序遍历的顺序是：左子树、当前节点、右子树。
示例：
4 / \ 2 6 / / \ 1 5 7输入：root = [4,2,6,1,null,5,7]输出：[1,2,4,5,6,7]其余例子略
讲解
基础概念
树是一种像倒过来的树一样的数据结构：从一个起点往下分叉。
节点就是树里的一个元素。每个节点通常会保存一个值，比如图里的 1、2、3。
根节点就是整棵树最上面的节点，也就是题目里的 root。如果 root = []，说明这棵树是空的。
二叉树表示每个节点最多有两个孩子：左孩子和右孩子。以某个节点的左孩子为起点继续往下看，就是它的左子树；以右孩子为起点继续往下看，就是它的右子树。
深度优先搜索就是先沿着一条路尽量往深处走，走不下去了再退回来换另一条路。二叉树的前序、中序、后序遍历都属于这种思路。
中序遍历专门指二叉树里的“左、根、右”：先访问左子树，再访问当前节点，最后访问右子树。
栈是LIFO。stack.append(x) 表示把 x 放进栈，stack.pop() 表示取出最后放进去的元素。
这道题的核心就是记住中序遍历的访问顺序：左、根、右。
递归法
递归法最直观，但要先注意一点：代码里的 root 不一定永远是整棵树最上面的根节点，它更像是“当前正在处理的节点”。
如果左边或右边没有节点，对应的 root.left 或 root.right 就是 None。
递归函数 inorder(root) 做的事情是：
- 如果当前节点是空的，直接返回。
- 先递归处理当前节点的左子树。
- 左边处理完以后，把当前节点的值加入结果。
- 最后递归处理当前节点的右子树。
以 root = [4,2,6,1,null,5,7] 为例：
执行过程可以简单看成：
inorder(4) inorder(4.left) -> inorder(2) inorder(2.left) -> inorder(1) inorder(1.left) -> 空，返回 加入 1 inorder(1.right) -> 空，返回 加入 2 inorder(2.right) -> 空，返回 加入 4 inorder(4.right) -> inorder(6) inorder(6.left) -> inorder(5) inorder(5.left) -> 空，返回 加入 5 inorder(5.right) -> 空，返回 加入 6 inorder(6.right) -> inorder(7) inorder(7.left) -> 空，返回 加入 7 inorder(7.right) -> 空，返回所以结果是 [1, 2, 4, 5, 6, 7]。
迭代栈法
递归本质上也在用系统调用栈。迭代法就是自己准备一个 stack 来模拟递归。
中序遍历是“左、根、右”，所以一个节点不能一看到就立刻加入结果，必须先把它左边的节点处理完。
栈里保存的就是这些“还不能访问，先等一下”的节点。
具体过程是：
- 当前节点不为空时，一直往左走，路过的节点都放进栈。
- 走到空节点，说明左边已经到底了。
- 从栈里
pop一个节点，这个节点的左边已经处理完，现在可以加入结果。 - 然后转向这个节点的右子树，继续重复。
以 root = [4,2,6,1,null,5,7] 为例：
4 / \ 2 6 / / \ 1 5 7执行过程可以简单看成：
while root or stack: while root: stack.append(root) root = root.left放入 4，往左到 2放入 2，往左到 1放入 1，往左到空
root = stack.pop()res.append(root.val)root = root.rightpop 1，加入 1，1 没有右边（跳出while root，继续执行上面）pop 2，加入 2，2 没有右边
pop 4，加入 4，转向 4 的右边 6
放入 6，往左到 5放入 5，往左到空pop 5，加入 5，5 没有右边
pop 6，加入 6，转向 6 的右边 7放入 7，往左到空pop 7，加入 7，7 没有右边所以结果是 [1, 2, 4, 5, 6, 7]。
复杂度
- 递归法：时间复杂度
O(n)，空间复杂度O(n) - 迭代栈法：时间复杂度
O(n)，空间复杂度O(n)
代码
递归法
源码
class Solution: def inorderTraversal(self, root: "TreeNode") -> list[int]: res = []
def inorder(root): if not root: return inorder(root.left) res.append(root.val) inorder(root.right)
inorder(root) return res迭代栈法
源码
class Solution: def inorderTraversal(self, root: "TreeNode") -> list[int]: res = [] stack = []
while root or stack: while root: stack.append(root) root = root.left
root = stack.pop() res.append(root.val) root = root.right
return res测试
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right
sol = Solution()
root = TreeNode(1)root.right = TreeNode(2)root.right.left = TreeNode(3)assert sol.inorderTraversal(root) == [1, 3, 2]
root = TreeNode(4)root.left = TreeNode(2)root.right = TreeNode(6)root.left.left = TreeNode(1)root.right.left = TreeNode(5)root.right.right = TreeNode(7)assert sol.inorderTraversal(root) == [1, 2, 4, 5, 6, 7]
root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)root.left.right.left = TreeNode(6)root.left.right.right = TreeNode(7)root.right.right = TreeNode(8)root.right.right.left = TreeNode(9)assert sol.inorderTraversal(root) == [4, 2, 6, 5, 7, 1, 3, 9, 8]
assert sol.inorderTraversal(None) == []assert sol.inorderTraversal(TreeNode(1)) == [1]
print("PASS")参考资料
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
评论区
音乐
暂未播放
