在二叉树中增加一行

🎯 问题描述

给定一个二叉树的根 root 和两个整数 val 和 depth，在给定的深度 depth 处添加一行值为 val 的节点。

  • 根节点 root 的深度为 1。
  • 添加规则：对于深度为 depth - 1 的每一非空节点 N，创建两个值为 val 的节点作为 N 的左右子树。N 原先的左子树作为新左节点的左子树，N 原先的右子树作为新右节点的右子树。
  • 特殊情况：如果 depth == 1，则创建一个新的根节点，原整棵树作为新根的左子树。

💻 解题思路

思路一：DFS 深度优先搜索（你的解法）

核心思想：利用递归向下遍历，当到达目标深度的上一层（即 depth - 1 层）时，进行节点的插入和指针的重新指向。

代码实现

from typing import Optional

# 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 addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        # 特殊情况：需要在根节点上方插入，直接“换头”
        if depth == 1:
            new_root = TreeNode(val)
            new_root.left = root
            return new_root

        def dfs(node: Optional[TreeNode], cur_depth: int) -> None:
            if not node:
                return
            # 到达目标深度的父节点层（depth - 1）
            if cur_depth == depth - 1:
                # 1. 保存原左右子树
                left_sub = node.left
                right_sub = node.right
                # 2. 创建新节点并插入
                node.left = TreeNode(val)
                node.right = TreeNode(val)
                # 3. 衔接原子树
                node.left.left = left_sub
                node.right.right = right_sub
                return
            # 继续向下递归
            dfs(node.left, cur_depth + 1)
            dfs(node.right, cur_depth + 1)

        dfs(root, 1)   # 根节点深度为1
        return root

📊 性能分析

  • 时间复杂度：O(n)O(n)。DFS 在最坏情况下需要遍历到目标层，最多访问 nn 个节点。
  • 空间复杂度：O(h)O(h)。DFS 取决于递归栈的深度（树高 hh）；

💡 思考

这道题是二叉树“指针操作”的经典题。

  1. DFS 解法：代码简洁，利用递归栈自然地下探到指定层级，非常适合处理这种“找到某一层并修改”的需求。
  2. 易错点：一定要记得先保存原节点的 left 和 right，否则直接覆盖后，原来的子树就丢失了。