树 DFS · Tree DFS

一句话骨架：写树 DFS 永远先问三个问题——① 当前节点要返回什么？② 我从子树拿到了什么？③ 我把什么传给了子树？三件事想清楚，递归就只是机械翻译。

三种递归形态

形态	例子	模式
归纳（自底向上）	树的高度	`return f(root.left) + f(root.right) + 1`
分治	翻转二叉树	子问题独立解决，再组合
带状态下传	路径求和	把累计值通过参数往下传

一个易错点

「DFS 返回值」与「全局答案」常常不是同一件事。最大路径和、二叉树直径等题里——返回的是「单边贡献给父亲」，更新全局的是「跨左右」。两条线必须分开。

关卡 1 · 二叉树的中序遍历

学习目标

能写递归三行版 + 迭代版（栈 + 一路向左），并理解 BST 中序为什么有序。

#94二叉树的中序遍历简单

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

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

递归实现简单，但请尝试用迭代实现（用栈模拟递归）——这是 BST 类题目的基础工具。

示例 1

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

输出[1,3,2]

示例 2

输入root = []

输出[]

示例 3

输入root = [1]

输出[1]

约束

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

💡 思路：中序 = 左 → 根 → 右。递归就是这三行的字面翻译。迭代版用栈：「一路向左压到底，弹一个就处理它，再转去右子树继续向左压」——这个动作用栈精确刻画了递归的隐式调用栈。

✅ 完整解法

时间 O(n) · 空间 O(h) h 为树高

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：递归 6def inorderTraversal(root: TreeNode | None) -> list[int]: 7    res = [] 8    def dfs(node: TreeNode | None) -> None: 9        if not node:10            return11        dfs(node.left)12        res.append(node.val)13        dfs(node.right)14    dfs(root)15    return res16 17# 解法二：迭代（栈 + 一路向左）18def inorderTraversalIter(root: TreeNode | None) -> list[int]:19    res, stack = [], []20    curr = root21    while curr or stack:22        # 1. 一路向左压栈23        while curr:24            stack.append(curr)25            curr = curr.left26        # 2. 弹一个并处理27        node = stack.pop()28        res.append(node.val)29        # 3. 转到右子树（继续走 1）30        curr = node.right31    return res

🐞 单步可视化

示例：root = [1, 2, 3, 4, 5]（解法二·迭代）

代码L20

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：递归 6def inorderTraversal(root: TreeNode | None) -> list[int]: 7    res = [] 8    def dfs(node: TreeNode | None) -> None: 9        if not node:10            return11        dfs(node.left)12        res.append(node.val)13        dfs(node.right)14    dfs(root)15    return res16 17# 解法二：迭代（栈 + 一路向左）18def inorderTraversalIter(root: TreeNode | None) -> list[int]:19    res, stack = [], []20    curr = root21    while curr or stack:22        # 1. 一路向左压栈23        while curr:24            stack.append(curr)25            curr = curr.left26        # 2. 弹一个并处理27        node = stack.pop()28        res.append(node.val)29        # 3. 转到右子树（继续走 1）30        curr = node.right31    return res

数据流

curr1stack.size0res[]

栈/递归

空

输出[]

1 / 32初始化 curr=root, stack=[]

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

中序遍历的访问顺序是？

递归终止条件 if not node: return 缺了会怎样？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：递归 6def inorderTraversal(root: TreeNode | None) -> list[int]: 7    res = [] 8    def dfs(node: TreeNode | None) -> None: 9        if not node:10            return11        dfs(node.left)12        res.append(node.val)13        dfs(node.right)14    dfs(root)15    return res16 17# 解法二：迭代（栈 + 一路向左）18def inorderTraversalIter(root: TreeNode | None) -> list[int]:19    res, stack = [], []20    curr = root21    while curr or stack:22        # 1. 一路向左压栈23        while curr:24            stack.append(curr)25            curr = curr.left26        # 2. 弹一个并处理27        node = stack.pop()28        res.append(node.val)29        # 3. 转到右子树（继续走 1）30        curr = node.right31    return res

迭代版中「一路向左压栈」的动作模拟了递归的什么？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：递归 6def inorderTraversal(root: TreeNode | None) -> list[int]: 7    res = [] 8    def dfs(node: TreeNode | None) -> None: 9        if not node:10            return11        dfs(node.left)12        res.append(node.val)13        dfs(node.right)14    dfs(root)15    return res16 17# 解法二：迭代（栈 + 一路向左）18def inorderTraversalIter(root: TreeNode | None) -> list[int]:19    res, stack = [], []20    curr = root21    while curr or stack:22        # 1. 一路向左压栈23        while curr:24            stack.append(curr)25            curr = curr.left26        # 2. 弹一个并处理27        node = stack.pop()28        res.append(node.val)29        # 3. 转到右子树（继续走 1）30        curr = node.right31    return res

迭代版退出循环的条件是什么？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：递归 6def inorderTraversal(root: TreeNode | None) -> list[int]: 7    res = [] 8    def dfs(node: TreeNode | None) -> None: 9        if not node:10            return11        dfs(node.left)12        res.append(node.val)13        dfs(node.right)14    dfs(root)15    return res16 17# 解法二：迭代（栈 + 一路向左）18def inorderTraversalIter(root: TreeNode | None) -> list[int]:19    res, stack = [], []20    curr = root21    while curr or stack:22        # 1. 一路向左压栈23        while curr:24            stack.append(curr)25            curr = curr.left26        # 2. 弹一个并处理27        node = stack.pop()28        res.append(node.val)29        # 3. 转到右子树（继续走 1）30        curr = node.right31    return res

弹出节点 node 后，curr = node.right 这一步意义？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：递归 6def inorderTraversal(root: TreeNode | None) -> list[int]: 7    res = [] 8    def dfs(node: TreeNode | None) -> None: 9        if not node:10            return11        dfs(node.left)12        res.append(node.val)13        dfs(node.right)14    dfs(root)15    return res16 17# 解法二：迭代（栈 + 一路向左）18def inorderTraversalIter(root: TreeNode | None) -> list[int]:19    res, stack = [], []20    curr = root21    while curr or stack:22        # 1. 一路向左压栈23        while curr:24            stack.append(curr)25            curr = curr.left26        # 2. 弹一个并处理27        node = stack.pop()28        res.append(node.val)29        # 3. 转到右子树（继续走 1）30        curr = node.right31    return res

空间复杂度 O(h) 中 h 是什么？最坏情况下 h 可能多大？

在 BST 上做中序遍历，输出会有什么特别？

递归版 res 用闭包变量比起作为参数传递有什么优势？

为什么递归版用 res.append(node.val) 而不是 return res + ...？

Python 默认递归深度大约多少？

把「中序」改成「前序」，递归版的改动是？

想把空间压到 O(1)（不计输出），可以用什么技巧？

关卡 2 · 二叉树中的最大路径和

学习目标

能讲清「返回单边 vs 更新全局跨左右」是两件事，并写出 self.ans 的正确语义。

#124二叉树中的最大路径和困难

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

二叉树中的路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root，返回其最大路径和。

示例 1

输入root = [1,2,3]

输出6

💡 路径 2 → 1 → 3，和为 6

示例 2

输入root = [-10,9,20,null,null,15,7]

输出42

💡 路径 15 → 20 → 7

示例 3

输入root = [-3]

输出-3

💡 单节点也是合法路径

约束

树中节点数目范围是 [1, 3 × 10⁴]
-1000 ≤ Node.val ≤ 1000

💡 思路：关键洞察：「DFS 返回值」与「全局最大答案」**不是同一件事**。返回值是「以本节点为端点向下走的最大单边和」（父节点要拿来续路径，只能选一边）；全局答案是「以本节点为顶点跨左右的最大路径和」（不会再向上延伸）。负贡献的子树直接 max(..., 0) 舍弃。

✅ 完整解法

时间 O(n) · 空间 O(h)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5class Solution: 6    def maxPathSum(self, root: TreeNode | None) -> int: 7        self.ans = float('-inf') 8  9        def gain(node: TreeNode | None) -> int:10            # 返回：以 node 为端点向下走的「最大单边和」11            if not node:12                return 013            # 子树负贡献则直接舍弃（取 0）——不向下延伸更优14            left = max(gain(node.left), 0)15            right = max(gain(node.right), 0)16            # 「以 node 为顶点跨左右」的路径和——拿来更新全局答案17            self.ans = max(self.ans, node.val + left + right)18            # 但**返回**只能选一边——因为父节点要把当前节点串入它的路径19            return node.val + max(left, right)20 21        gain(root)22        return self.ans

🐞 单步可视化

示例：root = [-10, 9, 20, null, null, 15, 7]（最大路径和 = 42）

代码L4

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5class Solution: 6    def maxPathSum(self, root: TreeNode | None) -> int: 7        self.ans = float('-inf') 8  9        def gain(node: TreeNode | None) -> int:10            # 返回：以 node 为端点向下走的「最大单边和」11            if not node:12                return 013            # 子树负贡献则直接舍弃（取 0）——不向下延伸更优14            left = max(gain(node.left), 0)15            right = max(gain(node.right), 0)16            # 「以 node 为顶点跨左右」的路径和——拿来更新全局答案17            self.ans = max(self.ans, node.val + left + right)18            # 但**返回**只能选一边——因为父节点要把当前节点串入它的路径19            return node.val + max(left, right)20 21        gain(root)22        return self.ans

数据流

currNoneleftGain-rightGain-newPath-maxSum-∞return-

-10

栈/递归

空

输出-∞

1 / 38初始化 maxSum = -∞，开始 dfs(-10)

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

本题最易错的概念是什么？

max(gain(node.left), 0) 这一行的意思？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5class Solution: 6    def maxPathSum(self, root: TreeNode | None) -> int: 7        self.ans = float('-inf') 8  9        def gain(node: TreeNode | None) -> int:10            # 返回：以 node 为端点向下走的「最大单边和」11            if not node:12                return 013            # 子树负贡献则直接舍弃（取 0）——不向下延伸更优14            left = max(gain(node.left), 0)15            right = max(gain(node.right), 0)16            # 「以 node 为顶点跨左右」的路径和——拿来更新全局答案17            self.ans = max(self.ans, node.val + left + right)18            # 但**返回**只能选一边——因为父节点要把当前节点串入它的路径19            return node.val + max(left, right)20 21        gain(root)22        return self.ans

self.ans = max(self.ans, node.val + left + right) 中为什么是 + left + right？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5class Solution: 6    def maxPathSum(self, root: TreeNode | None) -> int: 7        self.ans = float('-inf') 8  9        def gain(node: TreeNode | None) -> int:10            # 返回：以 node 为端点向下走的「最大单边和」11            if not node:12                return 013            # 子树负贡献则直接舍弃（取 0）——不向下延伸更优14            left = max(gain(node.left), 0)15            right = max(gain(node.right), 0)16            # 「以 node 为顶点跨左右」的路径和——拿来更新全局答案17            self.ans = max(self.ans, node.val + left + right)18            # 但**返回**只能选一边——因为父节点要把当前节点串入它的路径19            return node.val + max(left, right)20 21        gain(root)22        return self.ans

为什么返回时是 node.val + max(left, right)？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5class Solution: 6    def maxPathSum(self, root: TreeNode | None) -> int: 7        self.ans = float('-inf') 8  9        def gain(node: TreeNode | None) -> int:10            # 返回：以 node 为端点向下走的「最大单边和」11            if not node:12                return 013            # 子树负贡献则直接舍弃（取 0）——不向下延伸更优14            left = max(gain(node.left), 0)15            right = max(gain(node.right), 0)16            # 「以 node 为顶点跨左右」的路径和——拿来更新全局答案17            self.ans = max(self.ans, node.val + left + right)18            # 但**返回**只能选一边——因为父节点要把当前节点串入它的路径19            return node.val + max(left, right)20 21        gain(root)22        return self.ans

self.ans = float("-inf") 而不是 0 的原因？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5class Solution: 6    def maxPathSum(self, root: TreeNode | None) -> int: 7        self.ans = float('-inf') 8  9        def gain(node: TreeNode | None) -> int:10            # 返回：以 node 为端点向下走的「最大单边和」11            if not node:12                return 013            # 子树负贡献则直接舍弃（取 0）——不向下延伸更优14            left = max(gain(node.left), 0)15            right = max(gain(node.right), 0)16            # 「以 node 为顶点跨左右」的路径和——拿来更新全局答案17            self.ans = max(self.ans, node.val + left + right)18            # 但**返回**只能选一边——因为父节点要把当前节点串入它的路径19            return node.val + max(left, right)20 21        gain(root)22        return self.ans

为什么用 self.ans 而不是 nonlocal ans？

空节点 dfs 应返回什么？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5class Solution: 6    def maxPathSum(self, root: TreeNode | None) -> int: 7        self.ans = float('-inf') 8  9        def gain(node: TreeNode | None) -> int:10            # 返回：以 node 为端点向下走的「最大单边和」11            if not node:12                return 013            # 子树负贡献则直接舍弃（取 0）——不向下延伸更优14            left = max(gain(node.left), 0)15            right = max(gain(node.right), 0)16            # 「以 node 为顶点跨左右」的路径和——拿来更新全局答案17            self.ans = max(self.ans, node.val + left + right)18            # 但**返回**只能选一边——因为父节点要把当前节点串入它的路径19            return node.val + max(left, right)20 21        gain(root)22        return self.ans

本题的递归形态属于「DFS 三态」中的哪一种？

时间复杂度 O(n)，关键在于？

空间复杂度 O(h) 来自？

若把 self.ans = max(self.ans, node.val + left + right) 改成 node.val + max(left, right) 会怎样？

把 self.ans 改成局部变量 ans = -inf 然后在 dfs 里赋值，结果如何？

关卡 3 · 二叉树的最近公共祖先

学习目标

能用「后序回溯 + 三种情况」9 行写出 LCA，并迁移到 BST 优化版。

#236二叉树的最近公共祖先中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

给定一个二叉树，找到该树中两个指定节点的最近公共祖先（LCA）。

最近公共祖先的定义为：「对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。」

示例 1

输入root = [3,5,1,6,2,0,8,null,null,7,4], p=5, q=1

输出3

示例 2

输入root = [3,5,1,6,2,0,8,null,null,7,4], p=5, q=4

输出5

💡 5 是自己的祖先

示例 3

输入root = [1,2], p=1, q=2

输出1

约束

树中节点数目范围在 [2, 10⁵]
-10⁹ ≤ Node.val ≤ 10⁹
p ≠ q，p 和 q 均存在于树中

💡 思路：后序回溯。对每个节点问：「左子树能找到 p 或 q 吗？右子树呢？」——三种情况：① 两边都找到 → 当前节点就是 LCA；② 只一边找到 → 把那一边的结果上抛（要么是 p/q 本体，要么是更深处的 LCA）；③ 都没找到 → 返回 None。终止条件「撞到 p 或 q 立刻返回」是关键剪枝。

✅ 完整解法

时间 O(n) · 空间 O(h)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5def lowestCommonAncestor( 6    root: TreeNode | None, 7    p: TreeNode, 8    q: TreeNode, 9) -> TreeNode | None:10    # 终止条件：空 / 撞到 p / 撞到 q —— 把当前节点上抛11    if root is None or root is p or root is q:12        return root13    left = lowestCommonAncestor(root.left, p, q)14    right = lowestCommonAncestor(root.right, p, q)15    # 左右都「找到了」——当前节点就是 LCA16    if left and right:17        return root18    # 只有一边找到——把那一边的结果上抛（可能是 p、q 之一，也可能是子树里的 LCA）19    return left if left else right

🐞 单步可视化

示例：root = [3,5,1,6,2,0,8,#,#,7,4], p = 5, q = 1（LCA = 3）

代码L4

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5def lowestCommonAncestor( 6    root: TreeNode | None, 7    p: TreeNode, 8    q: TreeNode, 9) -> TreeNode | None:10    # 终止条件：空 / 撞到 p / 撞到 q —— 把当前节点上抛11    if root is None or root is p or root is q:12        return root13    left = lowestCommonAncestor(root.left, p, q)14    right = lowestCommonAncestor(root.right, p, q)15    # 左右都「找到了」——当前节点就是 LCA16    if left and right:17        return root18    # 只有一边找到——把那一边的结果上抛（可能是 p、q 之一，也可能是子树里的 LCA）19    return left if left else right

数据流

currNonep5q1left?-right?-self?-ret-LCA?

栈/递归

空

输出LCA=?

1 / 58初始化 ancestor = null，p=5, q=1，开始 dfs(3)

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

终止条件 root is p or root is q 撞到立刻返回 root，背后的语义是？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5def lowestCommonAncestor( 6    root: TreeNode | None, 7    p: TreeNode, 8    q: TreeNode, 9) -> TreeNode | None:10    # 终止条件：空 / 撞到 p / 撞到 q —— 把当前节点上抛11    if root is None or root is p or root is q:12        return root13    left = lowestCommonAncestor(root.left, p, q)14    right = lowestCommonAncestor(root.right, p, q)15    # 左右都「找到了」——当前节点就是 LCA16    if left and right:17        return root18    # 只有一边找到——把那一边的结果上抛（可能是 p、q 之一，也可能是子树里的 LCA）19    return left if left else right

左右递归都返回非空时，为什么当前 root 就是 LCA？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5def lowestCommonAncestor( 6    root: TreeNode | None, 7    p: TreeNode, 8    q: TreeNode, 9) -> TreeNode | None:10    # 终止条件：空 / 撞到 p / 撞到 q —— 把当前节点上抛11    if root is None or root is p or root is q:12        return root13    left = lowestCommonAncestor(root.left, p, q)14    right = lowestCommonAncestor(root.right, p, q)15    # 左右都「找到了」——当前节点就是 LCA16    if left and right:17        return root18    # 只有一边找到——把那一边的结果上抛（可能是 p、q 之一，也可能是子树里的 LCA）19    return left if left else right

只有 left 非空时，应该上抛什么？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5def lowestCommonAncestor( 6    root: TreeNode | None, 7    p: TreeNode, 8    q: TreeNode, 9) -> TreeNode | None:10    # 终止条件：空 / 撞到 p / 撞到 q —— 把当前节点上抛11    if root is None or root is p or root is q:12        return root13    left = lowestCommonAncestor(root.left, p, q)14    right = lowestCommonAncestor(root.right, p, q)15    # 左右都「找到了」——当前节点就是 LCA16    if left and right:17        return root18    # 只有一边找到——把那一边的结果上抛（可能是 p、q 之一，也可能是子树里的 LCA）19    return left if left else right

什么是「后序回溯」式递归？

为什么用 is 而不是 ==？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5def lowestCommonAncestor( 6    root: TreeNode | None, 7    p: TreeNode, 8    q: TreeNode, 9) -> TreeNode | None:10    # 终止条件：空 / 撞到 p / 撞到 q —— 把当前节点上抛11    if root is None or root is p or root is q:12        return root13    left = lowestCommonAncestor(root.left, p, q)14    right = lowestCommonAncestor(root.right, p, q)15    # 左右都「找到了」——当前节点就是 LCA16    if left and right:17        return root18    # 只有一边找到——把那一边的结果上抛（可能是 p、q 之一，也可能是子树里的 LCA）19    return left if left else right

若 p 在 q 的子树里，递归的执行轨迹是？

本算法时间复杂度是？

空间复杂度 O(h) 来自？

若题目改成「BST 的 LCA」，能不能写出更优解？

若 p 不在树里，本代码会怎样？

return left if left else right 这种写法叫？

面试时如果让你不用递归怎么做？

关卡 4 · 二叉树的序列化与反序列化

学习目标

能讲清「为什么前序+「#」哨兵就够了」，并用 deque 写出对称的反序列化。

#297二叉树的序列化与反序列化困难

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

序列化是将一个数据结构或对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例 1

输入root = [1,2,3,null,null,4,5]

输出[1,2,3,null,null,4,5]

💡 前序：1,2,#,#,3,4,#,#,5,#,#

示例 2

输入root = []

输出[]

示例 3

输入root = [1]

输出[1]

约束

树中节点数目范围是 [0, 10⁴]
-1000 ≤ Node.val ≤ 1000

💡 思路：前序遍历 + 把空节点显式写成「#」即可双射：前序天然定义了「先根、再左、再右」的顺序，加上空哨兵后任何一棵二叉树都唯一对应一个字符串。反序列化时按同样顺序消费 tokens，遇到「#」返回 None，否则建节点 + 递归建左右。

✅ 完整解法

时间 O(n) · 空间 O(n)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1from collections import deque 2  3class TreeNode: 4    def __init__(self, val=0, left=None, right=None): 5        self.val, self.left, self.right = val, left, right 6  7class Codec: 8    def serialize(self, root: TreeNode | None) -> str: 9        # 前序 DFS：空节点显式记成 「#」10        parts = []11        def dfs(node: TreeNode | None) -> None:12            if not node:13                parts.append('#')14                return15            parts.append(str(node.val))16            dfs(node.left)17            dfs(node.right)18        dfs(root)19        return ','.join(parts)20 21    def deserialize(self, data: str) -> TreeNode | None:22        # 用 deque 让 popleft 是 O(1)；前序消费序列23        tokens = deque(data.split(','))24        def build() -> TreeNode | None:25            tok = tokens.popleft()26            if tok == '#':27                return None28            node = TreeNode(int(tok))29            node.left = build()30            node.right = build()31            return node32        return build()

🐞 单步可视化

示例：root = [1, 2, 3, null, null, 4, 5]（前序 + null 序列化）

代码L4

 1from collections import deque 2  3class TreeNode: 4    def __init__(self, val=0, left=None, right=None): 5        self.val, self.left, self.right = val, left, right 6  7class Codec: 8    def serialize(self, root: TreeNode | None) -> str: 9        # 前序 DFS：空节点显式记成 「#」10        parts = []11        def dfs(node: TreeNode | None) -> None:12            if not node:13                parts.append('#')14                return15            parts.append(str(node.val))16            dfs(node.left)17            dfs(node.right)18        dfs(root)19        return ','.join(parts)20 21    def deserialize(self, data: str) -> TreeNode | None:22        # 用 deque 让 popleft 是 O(1)；前序消费序列23        tokens = deque(data.split(','))24        def build() -> TreeNode | None:25            tok = tokens.popleft()26            if tok == '#':27                return None28            node = TreeNode(int(tok))29            node.left = build()30            node.right = build()31            return node32        return build()

数据流

phaseserializecurrNonetokens[]cursor-

栈/递归

空

输出(空)

1 / 57阶段 1：serialize（前序 DFS，空节点写 "null"）

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

为什么单独的「前序」或「中序」无法反序列化二叉树，但加上「#」哨兵就可以？

deserialize 用 deque 而非 list 的原因？

 1from collections import deque 2  3class TreeNode: 4    def __init__(self, val=0, left=None, right=None): 5        self.val, self.left, self.right = val, left, right 6  7class Codec: 8    def serialize(self, root: TreeNode | None) -> str: 9        # 前序 DFS：空节点显式记成 「#」10        parts = []11        def dfs(node: TreeNode | None) -> None:12            if not node:13                parts.append('#')14                return15            parts.append(str(node.val))16            dfs(node.left)17            dfs(node.right)18        dfs(root)19        return ','.join(parts)20 21    def deserialize(self, data: str) -> TreeNode | None:22        # 用 deque 让 popleft 是 O(1)；前序消费序列23        tokens = deque(data.split(','))24        def build() -> TreeNode | None:25            tok = tokens.popleft()26            if tok == '#':27                return None28            node = TreeNode(int(tok))29            node.left = build()30            node.right = build()31            return node32        return build()

build 函数为什么不需要传 index 参数也能正确处理？

 1from collections import deque 2  3class TreeNode: 4    def __init__(self, val=0, left=None, right=None): 5        self.val, self.left, self.right = val, left, right 6  7class Codec: 8    def serialize(self, root: TreeNode | None) -> str: 9        # 前序 DFS：空节点显式记成 「#」10        parts = []11        def dfs(node: TreeNode | None) -> None:12            if not node:13                parts.append('#')14                return15            parts.append(str(node.val))16            dfs(node.left)17            dfs(node.right)18        dfs(root)19        return ','.join(parts)20 21    def deserialize(self, data: str) -> TreeNode | None:22        # 用 deque 让 popleft 是 O(1)；前序消费序列23        tokens = deque(data.split(','))24        def build() -> TreeNode | None:25            tok = tokens.popleft()26            if tok == '#':27                return None28            node = TreeNode(int(tok))29            node.left = build()30            node.right = build()31            return node32        return build()

为什么不能用 None 直接转字符串而要用「#」？

serialize 和 deserialize 用「同样的遍历顺序」是关键吗？

空树 root 是 None 时，serialize 输出是？

BFS（层序）+ 显式「#」也能实现序列化吗？

tokens.popleft() 在 build 里抛 IndexError 意味着？

本题时间复杂度是？

空间复杂度 O(n) 来自？

若 val 包含逗号或负号会出问题吗？

Python 里 ','.join(parts) 这种链式操作的优势？

 1from collections import deque 2  3class TreeNode: 4    def __init__(self, val=0, left=None, right=None): 5        self.val, self.left, self.right = val, left, right 6  7class Codec: 8    def serialize(self, root: TreeNode | None) -> str: 9        # 前序 DFS：空节点显式记成 「#」10        parts = []11        def dfs(node: TreeNode | None) -> None:12            if not node:13                parts.append('#')14                return15            parts.append(str(node.val))16            dfs(node.left)17            dfs(node.right)18        dfs(root)19        return ','.join(parts)20 21    def deserialize(self, data: str) -> TreeNode | None:22        # 用 deque 让 popleft 是 O(1)；前序消费序列23        tokens = deque(data.split(','))24        def build() -> TreeNode | None:25            tok = tokens.popleft()26            if tok == '#':27                return None28            node = TreeNode(int(tok))29            node.left = build()30            node.right = build()31            return node32        return build()

同 pattern 索引（hot100 同类题）

题号	题名	难度	关键变形
104	二叉树的最大深度	简单	归纳：max(left, right) + 1
226	翻转二叉树	简单	分治：交换 left/right，递归处理子树
101	对称二叉树	简单	双参 dfs(left, right)：镜像比较
543	二叉树的直径	简单	类 #124：返回单边深度，更新全局 left+right
108	将有序数组转换为平衡 BST	简单	中序逆向：取中点为根，递归构造
105	从前序与中序遍历构造二叉树	中等	前序定根、中序定左右；用 dict 加速找根
98	验证 BST	中等	中序输出递增；或下传 (lo, hi) 区间
230	BST 第 K 小的元素	中等	中序迭代（栈 + 一路向左），数到第 K 个
437	路径总和 III	中等	前缀和 + 哈希，类似「和为 K 的子数组」迁移到树

面试常踩

闭包变量不会被修改：dfs 内 ans = ... 不会影响外层 ans——必须 nonlocal 或挂在 self 上；可变对象（list/dict 的 .append）则不需要。
空节点的返回值要和递推自洽：最大路径和返回 0、最大深度返回 0、LCA 返回 None——选一个让外层 max/sum/condition 不需要特判的值。
比较节点用 is 不是 ==：节点 val 可能重复，is 判身份才稳。
递归默认深度 1000：链状树 10⁴ 节点会 RecursionError——可以 sys.setrecursionlimit 或改迭代。
BST 中序 = 有序：这是 #98、#108、#230 的金钥匙；记住能省一类题的设计成本。

树 DFS · Tree DFS ​

三种递归形态 ​

关卡 1 · 二叉树的中序遍历 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 2 · 二叉树中的最大路径和 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 3 · 二叉树的最近公共祖先 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 4 · 二叉树的序列化与反序列化 ​

📝 题目

✅ 完整解法

🧠 理解检验

同 pattern 索引（hot100 同类题） ​

面试常踩 ​

树 DFS · Tree DFS

三种递归形态

关卡 1 · 二叉树的中序遍历

关卡 2 · 二叉树中的最大路径和

关卡 3 · 二叉树的最近公共祖先

关卡 4 · 二叉树的序列化与反序列化

同 pattern 索引（hot100 同类题）

面试常踩