在二叉树中增加一行 图解题解

这道题到底在问什么

输入

root=[1,2,3], val=9, depth=2

输出

[1,9,9,2,null,null,3]

输入

root=[1,2,3], val=9, depth=1

输出

新节点当根,原树挂它左边

最优解：一步一步想明白

1. 3记住「DFS 找到 depth-1 层,每个节点左右各插一个 val、旧子树挂到新节点对应侧」,下面逐帧套它。
2. 4depth=3, val=99这是原树,共 3 层:根 50;第 2 层 30、80;第 3 层是 30 的左孩子 20、80 的右孩子 70。我们要在第 3 层插入一整行 99。
3. 5depth-1 = 2depth=3,要在第 3 层插一行,换个角度就是在第 depth-1=2 层的每个节点下动手。第 2 层有 30、80 两个节点(紫色),它们就是要插新孩子的目标。
4. 6d=1DFS 带着层号 d 走。当前在根 50,d=1,还没到 depth-1=2,所以这一层不动手,继续往左右孩子递归,去找第 2 层。
5. 7d=1 → d=2根这层不动手,就向它的左孩子 30、右孩子 80 各递归一层,d 变成 2。这两个节点都落在第 2 层,正是 depth-1,马上逐个处理。
6. 8d=2 = depth-1递归到 30,d=2 正好等于 depth-1,命中目标层。接下来要在 30 的左右各插一个 99。动手前先记住 30 原来的孩子。
7. 9old: 左 20 / 右 空30 原来的左孩子是 20(红色)、右孩子为空。等会儿插完新节点,这两段旧子树要分别挂到新左、新右节点下面,所以先记牢。
8. 10左 99 左孩子暂空第一步:在 30 的左边新建一个值 99 的节点(绿色),它现在的左孩子先留空。下一步把 30 原来的左子树接到它左边。
9. 1120 下移一层把 30 原来的左子树 20 挂到左 99 的左边。注意 20 整段往下挪了一层,值和结构都没变,只是位置降一层。30 的左边就接好了。
10. 12右 99 右孩子暂空第二步:在 30 的右边新建一个值 99 的节点。它的右孩子要接 30 原来的右子树,而 30 原来右孩子为空。
11. 13原右为空把 30 原来的右子树接到右 99 的右边。30 原来右孩子为空,所以右 99 的右边保持为空。30 的右边也接好了。
12. 14左右两个 99 都插好30 这个节点处理完:左右各多了一个 99,旧的 20 跟着左 99 下移,右 99 右边因为原来就空、保持为空。回到第 2 层,去看下一个目标 80。
13. 15d=2 = depth-1回到第 2 层,递归到 80,d=2 同样是 depth-1,又一个目标。和处理 30 一样,先看 80 原来的孩子,再左右各插一个 99。
14. 16old: 左 空 / 右 7080 原来的左孩子为空、右孩子是 70(红色)。插完新节点后,这个 70 要挂到新右节点下面。
15. 17左 99 左孩子为空在 80 的左边新建一个值 99 的节点。它的左孩子要接 80 原来的左子树,而 80 原来左孩子为空,所以左 99 的左边保持为空。
16. 18原左为空把 80 原来的左子树接到左 99 的左边。80 原来左孩子为空,所以左 99 的左边也保持空,左边接好了。
17. 19右 99 右孩子接旧右在 80 的右边新建一个值 99 的节点。它的右孩子要接 80 原来的右子树 70,下一步把 70 挂上去。
18. 2070 下移一层把 80 原来的右子树 70 挂到右 99 的右边,70 整段往下挪一层。至此 80 也处理完,第 2 层的两个目标都插好了。
19. 21树从 3 层变 4 层第 3 层一整行 99、99、99、99 全部插好(绿色),原来在第 3 层的 20、70 整段下移到了第 4 层。回头看,我们只走了一遍树找到 depth-1 层,再给每个节点左右各塞一个新节点,旧子树顺势下移,一遍就完成。
20. 22第 3 层 = 4 个 99数一下:第 3 层现在正好是 99、99、99、99 四个——第 2 层两个节点各贡献了 2 个,完全符合「加一行」;原来的 20、70 安静地待在第 4 层,值和相对位置都没乱。
21. 2399 当新根再看特例 depth=1:这时没有「上一层」可挂新节点。做法是先新建一个值 99 的节点(绿色),它将当新的根。
22. 24原树作左子树再把原来的整棵树(蓝色)作为新根 99 的左子树挂上去,右边留空。这就是 depth=1 的特判,代码里单独一行处理,通用递归覆盖不了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
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:
            return TreeNode(val, root, None)
        def dfs(node, d):
            if not node: return
            if d == depth - 1:
                node.left = TreeNode(val, node.left, None)
                node.right = TreeNode(val, None, node.right)
            else:
                dfs(node.left, d + 1); dfs(node.right, d + 1)
        dfs(root, 1)
        return root

#include <algorithm>
#include <climits>
#include <functional>
#include <iterator>
#include <numeric>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: TreeNode* addOneRow(TreeNode* root,int val,int depth){ if(depth==1)return new TreeNode(val,root,nullptr); function<void(TreeNode*,int)> dfs=[&](TreeNode*n,int d){ if(!n)return; if(d==depth-1){ n->left=new TreeNode(val,n->left,nullptr); n->right=new TreeNode(val,nullptr,n->right);} else {dfs(n->left,d+1); dfs(n->right,d+1);} }; dfs(root,1); return root; }};

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ public TreeNode addOneRow(TreeNode root,int val,int depth){ if(depth==1)return new TreeNode(val,root,null); dfs(root,1,val,depth); return root;} void dfs(TreeNode n,int d,int val,int depth){ if(n==null)return; if(d==depth-1){ n.left=new TreeNode(val,n.left,null); n.right=new TreeNode(val,null,n.right);} else {dfs(n.left,d+1,val,depth); dfs(n.right,d+1,val,depth);} } }

复杂度

面试官可能追问