給定一個(gè)二叉樹押逼，根節(jié)點(diǎn)為第1層，深度為 1惦界。在其第 d 層追加一行值為 v 的節(jié)點(diǎn)挑格。
添加規(guī)則：給定一個(gè)深度值 d （正整數(shù)），針對深度為 d-1 層的每一非空節(jié)點(diǎn) N沾歪，為 N 創(chuàng)建兩個(gè)值為 v 的左子樹和右子樹恕齐。
將 N 原先的左子樹，連接為新節(jié)點(diǎn) v 的左子樹；將 N 原先的右子樹显歧，連接為新節(jié)點(diǎn) v 的右子樹。
如果 d 的值為 1确镊，深度 d - 1 不存在士骤，則創(chuàng)建一個(gè)新的根節(jié)點(diǎn) v，原先的整棵樹將作為 v 的左子樹蕾域。
示例 1:
輸入:
二叉樹如下所示:
4
/ \
2 6
/ \ /
3 1 5
v = 1
d = 2
輸出:
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5
示例 2:
輸入:
二叉樹如下所示:
4
/
2
/ \
3 1
v = 1
d = 3
輸出:
4
/
2
/ \
1 1
/ \
3 1
注意:
- 1.輸入的深度值 d 的范圍是：[1拷肌，二叉樹最大深度 + 1]。
- 2.輸入的二叉樹至少有一個(gè)節(jié)點(diǎn)旨巷。
解答
/**
* Definition for a binary tree node.
* 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;
* }
* }
*/
class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) return new TreeNode(val, root, null);
TreeNode node;
int currLevelNodeNum = 1, nextLevelNodeNum = 0, currDepth = 1;
Queue<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
while (!nodeQueue.isEmpty()) {
node = nodeQueue.poll();
if (currDepth == depth-1) {
// 當(dāng)前層即為要插入一行的元素的上一行
node.left = new TreeNode(val, node.left, null);
node.right = new TreeNode(val, null, node.right);
}
if (currDepth < depth) {
if (node.left != null) { nodeQueue.add(node.left); nextLevelNodeNum++; }
if (node.right != null) { nodeQueue.add(node.right); nextLevelNodeNum++; }
}
if (--currLevelNodeNum == 0) {
if (currDepth == depth-1) break;
currLevelNodeNum = nextLevelNodeNum;
nextLevelNodeNum = 0;
currDepth++;
}
}
return root;
}
}
