Solutions CS101

Appearance

102.二叉树的层序遍历 ​

https://leetcode.cn/problems/binary-tree-level-order-traversal/

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

示例 1：

img
输入：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
python
# 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
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            level = []

            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(level)

        return result

没有使用队列，一层一层用 array

python
# 戴嘉震 24信科
from typing import List, Optional
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        result = []
        this_level = [root]
        while this_level:
            result.append([])
            new_level = []
            for node in this_level:
                result[-1].append(node.val)
                if node.left: new_level.append(node.left)
                if node.right: new_level.append(node.right)
            this_level = new_level
        return result


# 辅助函数：将列表转换为二叉树
def list_to_tree(lst: List[Optional[int]]) -> Optional[TreeNode]:
    if not lst:
        return None

    root = TreeNode(lst[0])
    queue = deque([root])
    i = 1

    while queue and i < len(lst):
        node = queue.popleft()

        # 处理左子节点
        if lst[i] is not None:
            node.left = TreeNode(lst[i])
            queue.append(node.left)
        i += 1

        # 处理右子节点
        if i < len(lst) and lst[i] is not None:
            node.right = TreeNode(lst[i])
            queue.append(node.right)
        i += 1

    return root


if __name__ == '__main__':
    sol = Solution()

    # 输入列表
    input_list = [3, 9, 20, None, None, 15, 7]

    # 将列表转换为二叉树
    root = list_to_tree(input_list)

    # 打印层次遍历结果
    print(sol.levelOrder(root))

思路：这题深搜也很简单

python
# 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
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans=[]
        def dfs(root,depth):
            if root:
                if len(ans)<depth:	# 如果当前层还没列表，就创建
                    ans.append([])
                ans[depth-1].append(root.val)	# 将当前节点值放入对应层
                dfs(root.left,depth+1)
                dfs(root.right,depth+1)
        dfs(root,1)
        return ans

🚀 DFS 解法思路分析（递归）

虽然“层序”通常用 BFS，但只要能记录层数（depth），DFS 也能分层。

核心思想：

  1. 定义 dfs(node, depth) 每访问一个节点，就知道它在第几层。
  2. 用 ans 保存每层的列表。 当 len(ans) < depth 时，说明这一层还没建列表 → ans.append([])。
  3. 把当前节点值加入对应层 → ans[depth-1].append(root.val)。
  4. 递归访问左右子树，层数加一。

🧠 调用过程举例

假设树结构：

    1
   / \
  2   3

执行顺序：

调用动作ans
dfs(1,1)新建第1层 → 加入[1][[1]]
dfs(2,2)新建第2层 → 加入[2][[1],[2]]
dfs(3,2)第2层已存在 → 加入[3][[1],[2,3]]

🔁 对比 BFS 写法（常规）

BFS 用队列，每次取出当前层的所有节点：

python
from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ans, queue = [], deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            ans.append(level)
        return ans

📘 小结

比较DFS 解法BFS 解法
关键结构递归 + depth队列 queue
思路深度优先但按层记录按层逐步遍历
优点简洁易写、递归清晰逻辑直观、符合“层序”语义
缺点深度大时递归栈可能溢出稍微冗长些

✅ 总结一句话： 虽然“层序遍历”传统上是 BFS，但 DFS 通过携带层号参数，也能优雅地实现同样效果。