一、题目
给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
注意，根节点 root 位于深度 1 。
加法规则如下:
- 给定整数
depth，对于深度为depth - 1的每个非空树节点cur，创建两个值为val的树节点作为cur的左子树根和右子树根。cur原来的左子树应该是新的左子树根的左子树。cur原来的右子树应该是新的右子树根的右子树。- 如果
depth == 1意味着depth - 1根本没有深度，那么创建一个树节点，值val作为整个原始树的新根，而原始树就是新根的左子树。
二、示例
2.1> 示例 1:
【输入】 root = [4,2,6,3,1,5], val = 1, depth = 2
【输出】 [4,1,1,2,null,null,6,3,1,5]
2.2> 示例 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
三、解题思路
3.1> 思路1：广度优先算法
根据题意，我们要在指定的某一层depth中添加一行指定的val值节点，那么很容易想到的解题思路就是广度优先算法。通过广度优先算法+队列，我们可以确定当前所遍历的层数，因为题意是要在depth层中添加一行val节点，其实主要修改节点之间的关系是在depth-1这一层中，所以，当我们遍历到depth-1这层的是，执行新节点的创建并维护到depth-1这层节点即可。
当然，在这个过程中，我们还需要针对一些特殊情况做特殊的处理，比如depth如果传值为1，那么意思就是，新的节点要替换老的root节点了。此时我们只需要在创建的新节点的左子节点维护原root节点即可。那么，另一种情况就是，当depth值时大于1的情况下，那么这种情况就可以使用通用的算法逻辑去处理了。依然是首先将root节点放入到队列Queue中，此时队列size等于1，那么我们通过for循环遍历这个size长度的节点，每当从队列中取到节点之后，都要再向Queue中放入自己的左右子节点，当然，如果左节点或者右节点有一个为null的话，就不用放入到Queue中了。
那么，每当遍历完一层节点之后，层数都要加1，当我们发现，当前遍历的层数等于depth-1的话，那么，就可以开始执行新建节点操作了。
下面我们以root = [4,2,6,3,1,5]，val = 1，depth = 3为例。首先，将root节点放入到队列Queue中，此时元素size=1，通过poll()方法遍历每个元素，由于此时层级是1，不满足depth-1，所以不需要创建新节点。具体操作如下所示：
随着我们对Node(4)的遍历，随着我们将其子节点Node(2)和Node(6)也放入到队列Queue中，此时队列 size=2，通过poll()方法遍历每个元素。
由于此时层级是2，满足了depth-1的条件，那么我们开始着手创建新的节点。根据题意，val值等于1，所以我们分别为Node(2)和Node(6)创建一共4个Node(1)，区别在于，这四个Node(1)的左右子节点是不同的，即：其中一个Node(1)的左子节点是Node(3)；另一个Node(1)的右子节点是Node(1)；第三个Node(1)的左子节点是Node(5)；最后一个Node(1)的左右子节点都为null。具体操作如下图所示：
通过对depth-1这层节点的操作，也就完成了我们整个业务逻辑了，我们将根节点进行返回即可。具体的代码实现，请参照：4.1> 实现1：广度优先算法
3.2> 思路2：深度优先算法
除了可以采用广度优先算法之外，我们也可以采用深度优先算法。那么当深度遍历到达depth-1这层的时候，我们就开始进行新节点的创建。此处与广度优先算法的区别就是，我们不再需要Queue这个队列结构了，而是通过对depth的计算，来确定是否到达了我们要操作的那一层。怎么计算呢？这里面其实会有一些绕。因为深度优先是从root根节点向下遍历的。而入参depth我们获得之后，要通过每次的减1操作，来计算是否满足我们要操作的那一层。他们之间别扭的点就在于，一个是从上往下，另一个是从下往上。那么问题来了，depth要减到什么情况下，才说明到达了我们要操作的那一层呢。其实是这样的：首先我们要操作的那层其实就是depth - 1这层。那么如果从根节点到达这层是需要往下走 (depth) - 1 - 1 = depth - 2 次 ，那么随着每次遍历，depth都会执行减1操作，也就是说，当depth - (depth - 2) = 2的时候，就到达了我们期望要操作的那一层了。即：if (depth == 2) 执行创建新节点的操作。
通过深度优先算法，可以全面提高代码执行效率和降低内存消耗。具体的代码实现，请参照：4.2> 实现2：深度优先算法
四、代码实现
4.1> 实现1：广度优先算法
class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) {
return new TreeNode(val, root, null);
}
Queue<TreeNode> queue = new ArrayDeque();
queue.add(root);
int searchDepth = 1;
while(!queue.isEmpty() && searchDepth != depth) {
// 因为下面else中会向queue中添加元素，所以，此处应该先计算出来循环的size大小，以免受到影响
int levelNodeSize = queue.size();
for (int i = 0; i < levelNodeSize; i++) {
TreeNode node = queue.poll();
if (searchDepth == (depth - 1)) {
node.left = new TreeNode(val, node.left, null);
node.right = new TreeNode(val, null, node.right);
} else {
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
searchDepth++;
}
return root;
}
}
4.2> 实现2：深度优先算法
class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (root == null) return null;
if (depth == 1) return new TreeNode(val, root, null);
if (depth == 2) {
root.left = new TreeNode(val, root.left, null);
root.right = new TreeNode(val, null, root.right);
} else {
addOneRow(root.left, val, depth - 1);
addOneRow(root.right, val, depth - 1);
}
return root;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
题目来源：力扣（LeetCode）
