LeetCode 623. 在二叉树中增加一行
题目描述
题意分析
根节点的深度为 $1$。要在深度
depth加入一行值为val的节点：对深度depth - 1的每个非空节点，创建新的左右孩子；原左子树接到新左孩子的左侧，原右子树接到新右孩子的右侧。若
depth = 1，则直接建立新根，整棵原树作为它的左子树。题目保证原树非空，插入深度不超过原树高度加一；树节点结构由平台提供。
解法：层序定位上一层后重新挂接
核心思路
[!blue]
插入一行只需要改变上一层节点的孩子指针，不需要遍历或重建原有子树内部。除新根这一特殊情况外，先用层序遍历找到深度
depth - 1的所有节点，再统一挂接新节点即可。初始队列只包含深度为 $1$ 的根。每轮把当前层的节点取出，将非空孩子收集为下一层，保持“本轮开始时，队列恰好保存这一层全部非空节点”的不变量。当队列中节点的深度达到
depth - 1时就停止，不再向下遍历。若depth = 2，初始根节点队列已经是目标层，不需要推进。Java 在每层开始时固定
queue.size()，本轮只取出这些原有节点，避免刚入队的下一层也被立即处理。Go 则把孩子放进独立的next切片，整层结束后再替换queue，达到相同的分层效果。对每个目标父节点，先创建新左、新右两个节点。将新左节点的左指针设为原左孩子，将新右节点的右指针设为原右孩子，然后让父节点指向这两个新节点。新左节点的右侧、新右节点的左侧保持为空；原子树中的所有连接都原样保留，只是整体向下移动一层。
挂接时必须读取旧孩子之后再覆盖父节点的指针。Java 先把旧引用放入新节点，再修改父节点；Go 的赋值会先求右侧构造表达式，所以
Left: node.Left、Right: node.Right取得的也是旧引用。只要父节点存在，就要创建两个新孩子，即使它原本缺少左子树或右子树；但上一层不存在的空位置不需要补父节点。插到原树高度加一时，就是给最深层的非空节点增加新叶子。若
depth = 1，单独创建一个新根并立即返回；其他情况返回原根引用。
解题步骤
- 若
depth == 1，创建值为val的新根，将原根接在左侧并返回。- 将原根放入队列，按完整层推进，直到队列表示深度
depth - 1。- 遍历这一层的每个节点，创建新左右孩子，并分别接住原左子树和原右子树。
- 将父节点的左右指针改为新节点，处理完后返回原根。
代码实现
class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) {
TreeNode node = new TreeNode(val);
node.left = root;
return node;
}
Deque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
for (int level = 1; level < depth - 1; level++) {
for (int size = queue.size(); size > 0; size--) {
TreeNode node = queue.remove();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
for (TreeNode node : queue) {
TreeNode left = new TreeNode(val);
TreeNode right = new TreeNode(val);
left.left = node.left;
right.right = node.right;
node.left = left;
node.right = right;
}
return root;
}
}
func addOneRow(root *TreeNode, val, depth int) *TreeNode {
if depth == 1 {
return &TreeNode{Val: val, Left: root}
}
queue := []*TreeNode{
root,
}
for level := 1; level < depth-1; level++ {
next := []*TreeNode{}
for _, node := range queue {
if node.Left != nil {
next = append(next, node.Left)
}
if node.Right != nil {
next = append(next, node.Right)
}
}
queue = next
}
for _, node := range queue {
node.Left = &TreeNode{Val: val, Left: node.Left}
node.Right = &TreeNode{Val: val, Right: node.Right}
}
return root
}
复杂度分析
- 时间复杂度：最坏 $O(n)$。只访问插入位置上一层及其之前的节点，每个目标父节点进行常数次挂接；
depth = 1时为 $O(1)$。- 空间复杂度：队列辅助空间为 $O(w)$，
w是原树的最大层宽。若目标上一层有p个非空节点，会新建2p个结果节点；新根情况只新建一个，新增结果节点不计入队列辅助空间。
关键点总结
[!green]
- 先完整定位上一层，再改指针，避免把刚插入的节点混入遍历。
- 原左子树只接到新左节点的左侧，原右子树只接到新右节点的右侧。
- 不改变旧子树内部结构，也不为不存在的上一层父节点补位置。
- 只有插入深度为 $1$ 时返回新根，其他情况继续返回原根。
易错点总结
[!yellow]
- 层序多推进一层，会把新节点插到错误深度；目标队列应停在
depth - 1。- Java 用不断变化的队列长度控制本轮，会将下一层节点一起处理。
- 先覆盖父节点孩子再读取旧引用，会丢失原子树或形成错误连接。
- 将原右子树接到新右节点的左侧，不符合题目规定的右侧挂接方式。
depth = 1时仍返回原根，会漏掉新增根节点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 复用按层遍历及层长快照，在目标上一层停止后进行指针插入。 |