在二叉树中增加一行

记住「DFS 找到 depth-1 层,每个节点左右各插一个 val、旧子树挂到新节点对应侧」,下面逐帧套它。

原树：这是原树,共 3 层:根 50;第 2 层 30、80;第 3 层是 30 的左孩子 20、80 的右孩子 70。我们要在第 3 层插入一整行 99。

找 depth-1 层：depth=3,要在第 3 层插一行,换个角度就是在第 depth-1=2 层的每个节点下动手。第 2 层有 30、80 两个节点(紫色),它们就是要插新孩子的目标。

DFS 从根出发：DFS 带着层号 d 走。当前在根 50,d=1,还没到 depth-1=2,所以这一层不动手,继续往左右孩子递归,去找第 2 层。

向两个孩子递归：根这层不动手,就向它的左孩子 30、右孩子 80 各递归一层,d 变成 2。这两个节点都落在第 2 层,正是 depth-1,马上逐个处理。

递归到 30：递归到 30,d=2 正好等于 depth-1,命中目标层。接下来要在 30 的左右各插一个 99。动手前先记住 30 原来的孩子。

记住 30 的原孩子：30 原来的左孩子是 20(红色)、右孩子为空。等会儿插完新节点,这两段旧子树要分别挂到新左、新右节点下面,所以先记牢。

30 左边新建 99：第一步:在 30 的左边新建一个值 99 的节点(绿色),它现在的左孩子先留空。下一步把 30 原来的左子树接到它左边。

旧左子树 20 挂到左 99：把 30 原来的左子树 20 挂到左 99 的左边。注意 20 整段往下挪了一层,值和结构都没变,只是位置降一层。30 的左边就接好了。

30 右边新建 99：第二步:在 30 的右边新建一个值 99 的节点。它的右孩子要接 30 原来的右子树,而 30 原来右孩子为空。

右 99 右边接旧右：把 30 原来的右子树接到右 99 的右边。30 原来右孩子为空,所以右 99 的右边保持为空。30 的右边也接好了。

30 处理完：30 这个节点处理完:左右各多了一个 99,旧的 20 跟着左 99 下移,右 99 右边因为原来就空、保持为空。回到第 2 层,去看下一个目标 80。

递归到 80：回到第 2 层,递归到 80,d=2 同样是 depth-1,又一个目标。和处理 30 一样,先看 80 原来的孩子,再左右各插一个 99。

记住 80 的原孩子：80 原来的左孩子为空、右孩子是 70(红色)。插完新节点后,这个 70 要挂到新右节点下面。

80 左边新建 99：在 80 的左边新建一个值 99 的节点。它的左孩子要接 80 原来的左子树,而 80 原来左孩子为空,所以左 99 的左边保持为空。

左 99 左边接旧左：把 80 原来的左子树接到左 99 的左边。80 原来左孩子为空,所以左 99 的左边也保持空,左边接好了。

80 右边新建 99：在 80 的右边新建一个值 99 的节点。它的右孩子要接 80 原来的右子树 70,下一步把 70 挂上去。

旧右子树 70 挂到右 99：把 80 原来的右子树 70 挂到右 99 的右边,70 整段往下挪一层。至此 80 也处理完,第 2 层的两个目标都插好了。

新行插好：第 3 层一整行 99、99、99、99 全部插好(绿色),原来在第 3 层的 20、70 整段下移到了第 4 层。回头看,我们只走了一遍树找到 depth-1 层,再给每个节点左右各塞一个新节点,旧子树顺势下移,一遍就完成。

数一数新结构：数一下:第 3 层现在正好是 99、99、99、99 四个——第 2 层两个节点各贡献了 2 个,完全符合「加一行」;原来的 20、70 安静地待在第 4 层,值和相对位置都没乱。

特例 depth=1:新建根：再看特例 depth=1:这时没有「上一层」可挂新节点。做法是先新建一个值 99 的节点(绿色),它将当新的根。

特例 depth=1:原树挂左：再把原来的整棵树(蓝色)作为新根 99 的左子树挂上去,右边留空。这就是 depth=1 的特判,代码里单独一行处理,通用递归覆盖不了。

边界:depth=1 新建根;depth=2 在根那层插;缺孩子则新节点对应侧为空。

两个追问:BFS 也行(逐层数到 depth-1);depth=1 必须特判新建根。