1.題目描述
給定一個二叉樹的根 root 和兩個整數(shù) val 和 depth 最爬，在給定的深度 depth 處添加一個值為 val 的節(jié)點行怜俐。
注意，根節(jié)點 root 位于深度 1 。
加法規(guī)則如下:
給定整數(shù) depth降瞳，對于深度為 depth - 1 的每個非空樹節(jié)點 cur 责静，創(chuàng)建兩個值為 val 的樹節(jié)點作為 cur 的左子樹根和右子樹根。
cur 原來的左子樹應該是新的左子樹根的左子樹憨奸。
cur 原來的右子樹應該是新的右子樹根的右子樹。
如果 depth == 1 意味著 depth - 1 根本沒有深度凿试，那么創(chuàng)建一個樹節(jié)點排宰，值 val 作為整個原始樹的新根，而原始樹就是新根的左子樹那婉。
示例 1:
輸入: root = [4,2,6,3,1,5], val = 1, depth = 2
輸出: [4,1,1,2,null,null,6,3,1,5]
示例 2:
輸入: root = [4,2,null,3,1], val = 1, depth = 3
輸出: [4,2,null,1,1,3,null,null,1]
2.解題思路與代碼
2.1 解題思路
這道題因為需要在指定深度的層上加一層板甘，所以考慮使用 BFS 進行解答。首先考慮當給定 depth 等于 1 的時候详炬，即要把 val 插入到根節(jié)點之上盐类，按照題目要求直接創(chuàng)建新的根節(jié)點 newRoot，并且讓新的根節(jié)點的 left 指向原來的根節(jié)點，即 newRoot.left = root在跳，代碼如下：
if (depth == 1) {
TreeNode newRoot = new TreeNode(val);
newRoot.left = root;
return newRoot;
}
接下來便開始處理 depth 大于 1 的情況枪萄，我們還是套用二叉樹 BFS 代碼公式進行解答。使用一個隊列存儲遍歷的節(jié)點硬毕，并使用變量 layer 和 count 分別統(tǒng)計遍歷的層數(shù)和放入隊列的次數(shù)呻引。首先進行初始化將根節(jié)點放入隊列中，因為根節(jié)點入隊因此此時 count 為 1吐咳，并且根據(jù)題目要求 layer 層數(shù)也是 1 逻悠。當放入隊列次數(shù)等于隊列大小的時候，表示一層已經(jīng)遍歷完了韭脊，此時層數(shù)加 1童谒，并且讓 count 歸零，代碼如下：
if (queue.size() == count) {
layer++;
count = 0;
}
這個時候我們從隊列中拿出第一個節(jié)點沪羔，此時判斷層數(shù) layer 是否等于 depth饥伊，如果不相等則將彈出節(jié)點的左右節(jié)點入棧；如果相等蔫饰，那么就需要使用 val 新建兩個節(jié)點琅豆，然后讓彈出節(jié)點的左右子樹指向新建節(jié)點，并且按照題目要求原來的左子樹應該是新的左子樹根的左子樹篓吁，右子樹應該是新的右子樹根的右子樹茫因，代碼如下：
if (layer == depth) {
TreeNode leftNode = new TreeNode(val);
TreeNode rightNode = new TreeNode(val);
leftNode.left = poll.left;
poll.left = leftNode;
rightNode.right = poll.right;
poll.right = rightNode;
}
需要注意的是我們需要在二叉樹的一層插入，所以上面的插入執(zhí)行完成之后不能夠退出循環(huán)杖剪，因為不能夠保證這一層是否遍歷完成冻押，只有當層數(shù) layer 大于 depth 的時候我們便可以退出循環(huán)結(jié)果返回根節(jié)點。
2.2 代碼
class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
// 在根節(jié)點插入上一層
if (depth == 1) {
TreeNode newRoot = new TreeNode(val);
newRoot.left = root;
return newRoot;
}
LinkedList<TreeNode> queue = new LinkedList<>();
int layer = 1;
int count = 1;
queue.offer(root);
while (!queue.isEmpty()) {
// queue.size() == count 時表示一層已經(jīng)遍歷完成盛嘿，遍歷完一層時層數(shù)加一洛巢，并且count歸零
if (queue.size() == count) {
layer++;
count = 0;
}
TreeNode poll = queue.poll();
// 插入新節(jié)點
if (layer == depth) {
TreeNode leftNode = new TreeNode(val);
TreeNode rightNode = new TreeNode(val);
leftNode.left = poll.left;
poll.left = leftNode;
rightNode.right = poll.right;
poll.right = rightNode;
}
// 層數(shù)大于 depth 時退出循環(huán)
if (layer > depth) {
break;
}
if (poll.left != null) {
queue.offer(poll.left);
count++;
}
if (poll.right != null) {
queue.offer(poll.right);
count++;
}
}
return root;
}
}
2.3 測試結(jié)果
通過測試
3.總結(jié)
- 使用二叉樹 BFS 進行解答
