1.题目基本信息

1.1.题目描述

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

注意，根节点 root 位于深度 1 。

加法规则如下:

• 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。

• cur 原来的左子树应该是新的左子树根的左子树。

• cur 原来的右子树应该是新的右子树根的右子树。

• 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。

1.2.题目地址

https://leetcode.cn/problems/add-one-row-to-tree/description/

2.解题方法

2.1.解题思路

广度优先搜索。搜索到第depth-1层的节点

2.2.解题步骤

第一步，树为空或者只有一层的情况处理

第二步，广搜获取第depth-1层的节点

第三步，遍历广搜的节点，并根据要求设置新的层

3.解题代码

python代码

from collections import deque

# 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]:
        # 思路：广度优先搜索。搜索到第depth-1层的节点
        # 第一步，树为空或者只有一层的情况处理
        if root is None:
            return root
        if depth == 1:
            return TreeNode(val, root, None)
        # 第二步，广搜获取第depth-1层的节点
        que = deque([root])
        arr = []
        steps = 0
        while que:
            steps += 1
            for _ in range(len(que)):
                node = que.popleft()
                if steps == depth - 1:
                    arr.append(node)
                if node.left is not None:
                    que.append(node.left)
                if node.right is not None:
                    que.append(node.right)
            if steps == depth + 1:
                break
        # 第三步，遍历广搜的节点，并根据要求设置新的层
        for node in arr:
            node.left = TreeNode(val, node.left, None)
            node.right = TreeNode(val, None, node.right)
        return root

4.执行结果