树 BFS · Tree BFS

一句话骨架：BFS 用 collections.deque 当队列，进入循环时先记下当前层的大小，把这一层全部弹出后再处理下一层。这「层级感」就是 BFS 的灵魂。

通用模板

python

from collections import deque
q = deque([root])
while q:
    size = len(q)            # 关键：当前层节点数
    level = []
    for _ in range(size):
        node = q.popleft()
        level.append(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    res.append(level)

为什么用 deque 不用 list

list.pop(0) 是 O(n)（要左移所有元素）；deque.popleft() 是 O(1)。BFS 涉及大量「从前端取」，用错容器直接 O(n²)。

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

学习目标

内化「先记 size 再 for size 次」的层级感模板；能讲清 deque vs list 的 O(1) vs O(n)。

#102二叉树的层序遍历中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

给你二叉树的根节点 root，返回其节点值的层序遍历（即逐层地，从左到右访问所有节点）。

输出形式是一个二维列表，每个内层列表是一层的节点值。

示例 1

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

输出[[3],[9,20],[15,7]]

示例 2

输入root = [1]

输出[[1]]

示例 3

输入root = []

输出[]

约束

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

💡 思路：BFS 模板的直接应用：用 deque 当队列，进入每轮循环时**先记下当前层的大小 `size`**，然后 for size 次只处理当前层的节点（同时把它们的子节点入队作为下一层）。这一行 `size = len(q)` 是层级感的灵魂——把「混在一起的下一层」与「正在处理的当前层」隔开。

✅ 完整解法

时间 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  7def levelOrder(root: TreeNode | None) -> list[list[int]]: 8    if not root: 9        return []10    res = []11    q = deque([root])12    while q:13        size = len(q)            # 关键：先记下当前层节点数14        level = []15        for _ in range(size):    # 只处理当前层这么多个16            node = q.popleft()17            level.append(node.val)18            if node.left:19                q.append(node.left)20            if node.right:21                q.append(node.right)22        res.append(level)23    return res

🐞 单步可视化

示例：root = [3, 9, 20, null, null, 15, 7]

代码L11

 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  7def levelOrder(root: TreeNode | None) -> list[list[int]]: 8    if not root: 9        return []10    res = []11    q = deque([root])12    while q:13        size = len(q)            # 关键：先记下当前层节点数14        level = []15        for _ in range(size):    # 只处理当前层这么多个16            node = q.popleft()17            level.append(node.val)18            if node.left:19                q.append(node.left)20            if node.right:21                q.append(node.right)22        res.append(level)23    return res

数据流

|queue|1

队列

输出

1 / 22初始化 q = deque([root=3])

速度

🧠 理解检验

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

BFS 树为什么用 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  7def levelOrder(root: TreeNode | None) -> list[list[int]]: 8    if not root: 9        return []10    res = []11    q = deque([root])12    while q:13        size = len(q)            # 关键：先记下当前层节点数14        level = []15        for _ in range(size):    # 只处理当前层这么多个16            node = q.popleft()17            level.append(node.val)18            if node.left:19                q.append(node.left)20            if node.right:21                q.append(node.right)22        res.append(level)23    return res

size = len(q) 这一行的意义是什么？

 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  7def levelOrder(root: TreeNode | None) -> list[list[int]]: 8    if not root: 9        return []10    res = []11    q = deque([root])12    while q:13        size = len(q)            # 关键：先记下当前层节点数14        level = []15        for _ in range(size):    # 只处理当前层这么多个16            node = q.popleft()17            level.append(node.val)18            if node.left:19                q.append(node.left)20            if node.right:21                q.append(node.right)22        res.append(level)23    return res

for 循环里能不能写 for _ in range(len(q)) 替代 size = len(q); for _ in range(size)？

if not root: return [] 必须放在最前面，原因是？

 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  7def levelOrder(root: TreeNode | None) -> list[list[int]]: 8    if not root: 9        return []10    res = []11    q = deque([root])12    while q:13        size = len(q)            # 关键：先记下当前层节点数14        level = []15        for _ in range(size):    # 只处理当前层这么多个16            node = q.popleft()17            level.append(node.val)18            if node.left:19                q.append(node.left)20            if node.right:21                q.append(node.right)22        res.append(level)23    return res

入队子节点时为什么要写 if node.left: 判断？

 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  7def levelOrder(root: TreeNode | None) -> list[list[int]]: 8    if not root: 9        return []10    res = []11    q = deque([root])12    while q:13        size = len(q)            # 关键：先记下当前层节点数14        level = []15        for _ in range(size):    # 只处理当前层这么多个16            node = q.popleft()17            level.append(node.val)18            if node.left:19                q.append(node.left)20            if node.right:21                q.append(node.right)22        res.append(level)23    return res

本题用 BFS 的好处相比 DFS 是？

本题空间复杂度 O(n) 主要来自？

若题目改成「锯齿形层序」（奇数层从右到左），最少改动是？

deque([root]) 这种初始化把整个 list 一次入队，等价于？

能不能用「记每个节点的 depth」一次循环输出，而不分两层 for？

本题时间复杂度是？

BFS 与 DFS 在「树高 h」与「最宽层 w」上的空间偏好？

关卡 2 · 二叉树的右视图

学习目标

能用 BFS 取每层最后一个 + DFS 先右后左两种思路解决，并说清「右视图 ≠ 最右链」。

#199二叉树的右视图中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

注意：是「每层最右侧能被看见的那一个」，不是「整棵树的最右链」——因为左子树深处的节点也可能比右子树短的部分更深。

示例 1

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

输出[1,3,4]

示例 2

输入root = [1,null,3]

输出[1,3]

示例 3

输入root = []

输出[]

约束

二叉树的节点个数的范围是 [0, 100]
-100 ≤ Node.val ≤ 100

💡 思路：两条主流：① BFS 按层处理，每层取最后一个节点（i == size - 1）；② DFS 先右后左，每个 depth 第一次被访问到时就是右视图的那个节点。两种写法都 O(n)。注意「最右链」不是右视图——若左子树比右子树深，最深那层的右视图来自左子树。

✅ 完整解法

时间 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  7# 解法一：BFS 取每层最后一个 8def rightSideView(root: TreeNode | None) -> list[int]: 9    if not root:10        return []11    res = []12    q = deque([root])13    while q:14        size = len(q)15        for i in range(size):16            node = q.popleft()17            if i == size - 1:           # 当前层最后一个 = 右视图能看到的18                res.append(node.val)19            if node.left:20                q.append(node.left)21            if node.right:22                q.append(node.right)23    return res24 25# 解法二：DFS 先右后左，按 depth 第一次见到才记录26def rightSideViewDFS(root: TreeNode | None) -> list[int]:27    res = []28    def dfs(node: TreeNode | None, depth: int) -> None:29        if not node:30            return31        if depth == len(res):           # 这一层第一次被访问到32            res.append(node.val)33        dfs(node.right, depth + 1)      # 关键：先右后左34        dfs(node.left, depth + 1)35    dfs(root, 0)36    return res

🐞 单步可视化

示例：root = [1, 2, 3, null, 5, null, 4]（右视图 = [1,3,4]）

代码L6

 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  7# 解法一：BFS 取每层最后一个 8def rightSideView(root: TreeNode | None) -> list[int]: 9    if not root:10        return []11    res = []12    q = deque([root])13    while q:14        size = len(q)15        for i in range(size):16            node = q.popleft()17            if i == size - 1:           # 当前层最后一个 = 右视图能看到的18                res.append(node.val)19            if node.left:20                q.append(node.left)21            if node.right:22                q.append(node.right)23    return res24 25# 解法二：DFS 先右后左，按 depth 第一次见到才记录26def rightSideViewDFS(root: TreeNode | None) -> list[int]:27    res = []28    def dfs(node: TreeNode | None, depth: int) -> None:29        if not node:30            return31        if depth == len(res):           # 这一层第一次被访问到32            res.append(node.val)33        dfs(node.right, depth + 1)      # 关键：先右后左34        dfs(node.left, depth + 1)35    dfs(root, 0)36    return res

数据流

|queue|1view[]右视图节点-

队列

输出[]

1 / 28初始化 q = [root=1]，view = []

速度

🧠 理解检验

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

为什么 BFS 解法取「每层最后一个」就是右视图？

 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  7# 解法一：BFS 取每层最后一个 8def rightSideView(root: TreeNode | None) -> list[int]: 9    if not root:10        return []11    res = []12    q = deque([root])13    while q:14        size = len(q)15        for i in range(size):16            node = q.popleft()17            if i == size - 1:           # 当前层最后一个 = 右视图能看到的18                res.append(node.val)19            if node.left:20                q.append(node.left)21            if node.right:22                q.append(node.right)23    return res24 25# 解法二：DFS 先右后左，按 depth 第一次见到才记录26def rightSideViewDFS(root: TreeNode | None) -> list[int]:27    res = []28    def dfs(node: TreeNode | None, depth: int) -> None:29        if not node:30            return31        if depth == len(res):           # 这一层第一次被访问到32            res.append(node.val)33        dfs(node.right, depth + 1)      # 关键：先右后左34        dfs(node.left, depth + 1)35    dfs(root, 0)36    return res

「右视图」是不是「树的最右一条链」？

DFS 解法为什么要「先右后左」？

 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  7# 解法一：BFS 取每层最后一个 8def rightSideView(root: TreeNode | None) -> list[int]: 9    if not root:10        return []11    res = []12    q = deque([root])13    while q:14        size = len(q)15        for i in range(size):16            node = q.popleft()17            if i == size - 1:           # 当前层最后一个 = 右视图能看到的18                res.append(node.val)19            if node.left:20                q.append(node.left)21            if node.right:22                q.append(node.right)23    return res24 25# 解法二：DFS 先右后左，按 depth 第一次见到才记录26def rightSideViewDFS(root: TreeNode | None) -> list[int]:27    res = []28    def dfs(node: TreeNode | None, depth: int) -> None:29        if not node:30            return31        if depth == len(res):           # 这一层第一次被访问到32            res.append(node.val)33        dfs(node.right, depth + 1)      # 关键：先右后左34        dfs(node.left, depth + 1)35    dfs(root, 0)36    return res

DFS 解法用 depth == len(res) 判断这一层是否第一次出现，原理是？

 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  7# 解法一：BFS 取每层最后一个 8def rightSideView(root: TreeNode | None) -> list[int]: 9    if not root:10        return []11    res = []12    q = deque([root])13    while q:14        size = len(q)15        for i in range(size):16            node = q.popleft()17            if i == size - 1:           # 当前层最后一个 = 右视图能看到的18                res.append(node.val)19            if node.left:20                q.append(node.left)21            if node.right:22                q.append(node.right)23    return res24 25# 解法二：DFS 先右后左，按 depth 第一次见到才记录26def rightSideViewDFS(root: TreeNode | None) -> list[int]:27    res = []28    def dfs(node: TreeNode | None, depth: int) -> None:29        if not node:30            return31        if depth == len(res):           # 这一层第一次被访问到32            res.append(node.val)33        dfs(node.right, depth + 1)      # 关键：先右后左34        dfs(node.left, depth + 1)35    dfs(root, 0)36    return res

若把 BFS 解法的入队顺序改成「先右后左」，要怎么改才能仍正确？

if not root: return [] 缺失会发生什么？

 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  7# 解法一：BFS 取每层最后一个 8def rightSideView(root: TreeNode | None) -> list[int]: 9    if not root:10        return []11    res = []12    q = deque([root])13    while q:14        size = len(q)15        for i in range(size):16            node = q.popleft()17            if i == size - 1:           # 当前层最后一个 = 右视图能看到的18                res.append(node.val)19            if node.left:20                q.append(node.left)21            if node.right:22                q.append(node.right)23    return res24 25# 解法二：DFS 先右后左，按 depth 第一次见到才记录26def rightSideViewDFS(root: TreeNode | None) -> list[int]:27    res = []28    def dfs(node: TreeNode | None, depth: int) -> None:29        if not node:30            return31        if depth == len(res):           # 这一层第一次被访问到32            res.append(node.val)33        dfs(node.right, depth + 1)      # 关键：先右后左34        dfs(node.left, depth + 1)35    dfs(root, 0)36    return res

BFS 和 DFS 两种解法时间复杂度是？

若题目变成「左视图」，BFS 解法最简单的改动？

DFS 解法的空间复杂度（不计输出）？

为什么 BFS 解法在 if i == size - 1 时才 append，而不是每个节点都 append？

把 DFS 解法的「先右后左」改成「先左后右」会怎样？

本题最坏的「时间 × 空间」复杂度组合？

关卡 3 · 二叉树展开为链表

学习目标

掌握 O(1) 额外空间的「左子树最右节点接右子树」技巧；理解 BFS / DFS / 迭代为何在本题殊途同归。

#114二叉树展开为链表中等

♥♥♥♥♥+0 XP🔥 0

0 / 13

📝 题目

给你二叉树的根节点 root，请你将它展开为一个单链表：

- 展开后的单链表应该同样使用 TreeNode，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null
- 展开后的单链表应该与二叉树的前序遍历顺序相同

要求原地完成，进阶：用 O(1) 额外空间。

示例 1

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

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

示例 2

输入root = []

输出[]

示例 3

输入root = [0]

输出[0]

约束

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

💡 思路：主流 O(1) 空间技巧：对每个有左子树的节点，把它的**右子树整体**挂到**左子树的最右节点**之下，然后把左子树搬到右、左置空。结果整棵树就按前序「拉直」。这其实是 Morris 遍历的同款思路。也可以用前序 DFS 写，但需要 O(h) 栈空间。

✅ 完整解法

时间 O(n) · 空间 O(1) 迭代版

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

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：O(1) 额外空间——「左子树最右节点接右子树」技巧 6def flatten(root: TreeNode | None) -> None: 7    curr = root 8    while curr: 9        if curr.left:10            # 找当前节点左子树的「最右节点」11            rightmost = curr.left12            while rightmost.right:13                rightmost = rightmost.right14            # 把原右子树挂到「最右节点」的右边15            rightmost.right = curr.right16            # 把左子树整体搬到右17            curr.right = curr.left18            curr.left = None19        curr = curr.right          # 进入下一节点（已经是展平后的下一个）20 21# 解法二：递归（前序）22def flattenRec(root: TreeNode | None) -> None:23    def dfs(node: TreeNode | None) -> TreeNode | None:24        # 返回展平后的「尾节点」25        if not node:26            return None27        left_tail = dfs(node.left)28        right_tail = dfs(node.right)29        if left_tail:30            left_tail.right = node.right31            node.right = node.left32            node.left = None33        return right_tail or left_tail or node

🐞 单步可视化

示例：root = [1, 2, 5, 3, 4, null, 6]（O(1) 空间扁平化）

代码L4

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：O(1) 额外空间——「左子树最右节点接右子树」技巧 6def flatten(root: TreeNode | None) -> None: 7    curr = root 8    while curr: 9        if curr.left:10            # 找当前节点左子树的「最右节点」11            rightmost = curr.left12            while rightmost.right:13                rightmost = rightmost.right14            # 把原右子树挂到「最右节点」的右边15            rightmost.right = curr.right16            # 把左子树整体搬到右17            curr.right = curr.left18            curr.left = None19        curr = curr.right          # 进入下一节点（已经是展平后的下一个）20 21# 解法二：递归（前序）22def flattenRec(root: TreeNode | None) -> None:23    def dfs(node: TreeNode | None) -> TreeNode | None:24        # 返回展平后的「尾节点」25        if not node:26            return None27        left_tail = dfs(node.left)28        right_tail = dfs(node.right)29        if left_tail:30            left_tail.right = node.right31            node.right = node.left32            node.left = None33        return right_tail or left_tail or node

数据流

curr1pre-阶段初始化

输出1 -> 5 -> 6

1 / 30初始化 curr = root

速度

🧠 理解检验

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

为什么这道题挂在 tree-bfs 关卡——它和 BFS 有什么关系？

「左子树最右节点接右子树」这一招的核心思想？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：O(1) 额外空间——「左子树最右节点接右子树」技巧 6def flatten(root: TreeNode | None) -> None: 7    curr = root 8    while curr: 9        if curr.left:10            # 找当前节点左子树的「最右节点」11            rightmost = curr.left12            while rightmost.right:13                rightmost = rightmost.right14            # 把原右子树挂到「最右节点」的右边15            rightmost.right = curr.right16            # 把左子树整体搬到右17            curr.right = curr.left18            curr.left = None19        curr = curr.right          # 进入下一节点（已经是展平后的下一个）20 21# 解法二：递归（前序）22def flattenRec(root: TreeNode | None) -> None:23    def dfs(node: TreeNode | None) -> TreeNode | None:24        # 返回展平后的「尾节点」25        if not node:26            return None27        left_tail = dfs(node.left)28        right_tail = dfs(node.right)29        if left_tail:30            left_tail.right = node.right31            node.right = node.left32            node.left = None33        return right_tail or left_tail or node

迭代版的时间复杂度是？分析关键？

迭代版空间复杂度真的是 O(1) 吗？

展平后所有节点的 left 应该是？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：O(1) 额外空间——「左子树最右节点接右子树」技巧 6def flatten(root: TreeNode | None) -> None: 7    curr = root 8    while curr: 9        if curr.left:10            # 找当前节点左子树的「最右节点」11            rightmost = curr.left12            while rightmost.right:13                rightmost = rightmost.right14            # 把原右子树挂到「最右节点」的右边15            rightmost.right = curr.right16            # 把左子树整体搬到右17            curr.right = curr.left18            curr.left = None19        curr = curr.right          # 进入下一节点（已经是展平后的下一个）20 21# 解法二：递归（前序）22def flattenRec(root: TreeNode | None) -> None:23    def dfs(node: TreeNode | None) -> TreeNode | None:24        # 返回展平后的「尾节点」25        if not node:26            return None27        left_tail = dfs(node.left)28        right_tail = dfs(node.right)29        if left_tail:30            left_tail.right = node.right31            node.right = node.left32            node.left = None33        return right_tail or left_tail or node

curr 推进到 curr.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# 解法一：O(1) 额外空间——「左子树最右节点接右子树」技巧 6def flatten(root: TreeNode | None) -> None: 7    curr = root 8    while curr: 9        if curr.left:10            # 找当前节点左子树的「最右节点」11            rightmost = curr.left12            while rightmost.right:13                rightmost = rightmost.right14            # 把原右子树挂到「最右节点」的右边15            rightmost.right = curr.right16            # 把左子树整体搬到右17            curr.right = curr.left18            curr.left = None19        curr = curr.right          # 进入下一节点（已经是展平后的下一个）20 21# 解法二：递归（前序）22def flattenRec(root: TreeNode | None) -> None:23    def dfs(node: TreeNode | None) -> TreeNode | None:24        # 返回展平后的「尾节点」25        if not node:26            return None27        left_tail = dfs(node.left)28        right_tail = dfs(node.right)29        if left_tail:30            left_tail.right = node.right31            node.right = node.left32            node.left = None33        return right_tail or left_tail or node

若 curr 没有左子树，会怎样？

 1class TreeNode: 2    def __init__(self, val=0, left=None, right=None): 3        self.val, self.left, self.right = val, left, right 4  5# 解法一：O(1) 额外空间——「左子树最右节点接右子树」技巧 6def flatten(root: TreeNode | None) -> None: 7    curr = root 8    while curr: 9        if curr.left:10            # 找当前节点左子树的「最右节点」11            rightmost = curr.left12            while rightmost.right:13                rightmost = rightmost.right14            # 把原右子树挂到「最右节点」的右边15            rightmost.right = curr.right16            # 把左子树整体搬到右17            curr.right = curr.left18            curr.left = None19        curr = curr.right          # 进入下一节点（已经是展平后的下一个）20 21# 解法二：递归（前序）22def flattenRec(root: TreeNode | None) -> None:23    def dfs(node: TreeNode | None) -> TreeNode | None:24        # 返回展平后的「尾节点」25        if not node:26            return None27        left_tail = dfs(node.left)28        right_tail = dfs(node.right)29        if left_tail:30            left_tail.right = node.right31            node.right = node.left32            node.left = None33        return right_tail or left_tail or node

另一种递归思路是「逆前序（右-左-根）」——它怎么帮我们构造？

若用「前序 BFS 把所有节点收进 list 再串起来」，会怎样？

while rightmost.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# 解法一：O(1) 额外空间——「左子树最右节点接右子树」技巧 6def flatten(root: TreeNode | None) -> None: 7    curr = root 8    while curr: 9        if curr.left:10            # 找当前节点左子树的「最右节点」11            rightmost = curr.left12            while rightmost.right:13                rightmost = rightmost.right14            # 把原右子树挂到「最右节点」的右边15            rightmost.right = curr.right16            # 把左子树整体搬到右17            curr.right = curr.left18            curr.left = None19        curr = curr.right          # 进入下一节点（已经是展平后的下一个）20 21# 解法二：递归（前序）22def flattenRec(root: TreeNode | None) -> None:23    def dfs(node: TreeNode | None) -> TreeNode | None:24        # 返回展平后的「尾节点」25        if not node:26            return None27        left_tail = dfs(node.left)28        right_tail = dfs(node.right)29        if left_tail:30            left_tail.right = node.right31            node.right = node.left32            node.left = None33        return right_tail or left_tail or node

本题不变量是？（每次循环结束时）

为什么这种「修改原指针」的做法在 Python 中安全？

展开顺序与哪种遍历一致？

同 pattern 索引（hot100 同类题）

题号	题名	难度	关键变形
104	二叉树的最大深度	简单	既可 DFS 归纳，也可 BFS 数层数——双解题
222	完全二叉树的节点个数	中等	不是裸 BFS——利用「完全二叉树」性质 + 二分树高，O(log² n)
116	填充每个节点的下一个右侧节点指针	中等	BFS 按层连 next；进阶版 O(1) 空间用「父层的 next 指引子层」

面试常踩

size = len(q) 漏写：队列里同时混着当前层和下一层，会把分层弄成扁平输出。
None 进队：忘写 if node.left: 判断会让 None 入队，下一轮 node.val 抛 AttributeError。
入队顺序决定层内方向：先左后右 → 层内从左到右；想要「左视图/右视图」改判断条件 i == 0 或 i == size - 1 即可。
BFS vs DFS 空间偏好：BFS 是 O(w)（最宽层），DFS 是 O(h)（树高）；瘦高树 DFS 省空间、矮宽树 DFS 也省（满二叉树最后一层 ≈ n/2）。

树 BFS · Tree BFS ​

通用模板 ​

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

📝 题目

✅ 完整解法

🧠 理解检验

关卡 2 · 二叉树的右视图 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 3 · 二叉树展开为链表 ​

📝 题目

✅ 完整解法

🧠 理解检验

同 pattern 索引（hot100 同类题） ​

面试常踩 ​

树 BFS · Tree BFS

通用模板

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

关卡 2 · 二叉树的右视图

关卡 3 · 二叉树展开为链表

同 pattern 索引（hot100 同类题）

面试常踩