原创 博哥

问题描述

来源：LeetCode第623题

难度：中等

给定一个二叉树的根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]

示例 1:

输入: 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<=105
• 1<=depth<=the depth of tree+1

节点类如下

public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode() {
}

TreeNode(int val) {
this.val = val;
}

TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}

广度优先搜索

这题是说的在第depth层添加一行，我们只需要找到第depth层节点的父节点即可，然后给这个父节点添加子节点，如下图所示。

原理比较简单，我们来看下代码

public TreeNode addOneRow(TreeNode root, int val, int depth) {
// 如果depth为1，相当于添加根节点
if (depth == 1)
return new TreeNode(val, root, null);

Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 记录第几层
depth--;
// 每层节点的个数
int size = queue.size();
while (size-- > 0) {
TreeNode cur = queue.poll();
if (depth == 1) {
// 这里cur是第depth层的父节点
cur.left = new TreeNode(val, cur.left, null);
cur.right = new TreeNode(val, null, cur.right);
} else {
// 左右子节点如果不为空，就分别添加到队列中
if (cur.left != null)
queue.offer(cur.left);
if (cur.right != null)
queue.offer(cur.right);
}
}
// 添加完，终止循环
if (depth == 1)
return root;
}
return null;
}

深度优先搜索

当然这题还可以使用深度优先搜索，从上往下遍历，到深度为depth-1的时候，把该深度的所有子节点添加一行新的节点，代码如下

public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1)
return new TreeNode(val, root, null);
return helper(root, val, depth - 1);
}

private TreeNode helper(TreeNode root, int val, int depth) {
if (root == null)
return null;
if (depth == 1) {
// 这里root是第depth层的父节点，要给他添加子节点
root.left = new TreeNode(val, root.left, null);
root.right = new TreeNode(val, null, root.right);
return root;
}
root.left = helper(root.left, val, depth - 1);
root.right = helper(root.right, val, depth - 1);
return root;
}