LeetCode 题解工作台
在二叉树中增加一行
给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。 注意，根节点 root 位于深度 1 。 加法规则如下: 给定整数 depth ，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
class Solution: def addOneRow(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
注意，根节点 root 位于深度 1 。
加法规则如下:
- 给定整数
depth，对于深度为depth - 1的每个非空树节点cur，创建两个值为val的树节点作为cur的左子树根和右子树根。 cur原来的左子树应该是新的左子树根的左子树。cur原来的右子树应该是新的右子树根的右子树。- 如果
depth == 1意味着depth - 1根本没有深度，那么创建一个树节点，值val作为整个原始树的新根，而原始树就是新根的左子树。
示例 1:
输入: root = [4,2,6,3,1,5], val = 1, depth = 2 输出: [4,1,1,2,null,null,6,3,1,5]
示例 2:
输入: root = [4,2,null,3,1], val = 1, depth = 3 输出: [4,2,null,1,1,3,null,null,1]
提示:
- 节点数在
[1, 104]范围内 - 树的深度在
[1, 104]范围内 -100 <= Node.val <= 100-105 <= val <= 1051 <= depth <= the depth of tree + 1
解题思路
方法一：DFS
# 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]:
def dfs(root, d):
if root is None:
return
if d == depth - 1:
root.left = TreeNode(val, root.left, None)
root.right = TreeNode(val, None, root.right)
return
dfs(root.left, d + 1)
dfs(root.right, d + 1)
if depth == 1:
return TreeNode(val, root)
dfs(root, 1)
return root
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexities vary depending on the chosen approach. A DFS approach typically has a time complexity of O(N) where N is the number of nodes, and space complexity can range from O(H) to O(N) based on the recursion stack or queue size. BFS usually has O(N) time and O(N) space complexity due to the level-order traversal and queue operations. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to identify the most efficient traversal method for tree modifications.
- question_mark
Proficiency in managing binary-tree relationships while maintaining integrity.
- question_mark
Strong understanding of binary-tree operations and performance considerations.
常见陷阱
外企场景- error
Incorrectly handling depth 1 insertion by not adjusting the root.
- error
Failing to manage left and right children properly when inserting nodes.
- error
Not accounting for edge cases where the depth exceeds the tree's current depth.
进阶变体
外企场景- arrow_right_alt
Modify the tree at a given depth with multiple values for nodes instead of a single value.
- arrow_right_alt
Allow dynamic depth changes while performing insertions at various levels.
- arrow_right_alt
Handle unbalanced trees by adding rows at varying depths.