623 Add One Row to Tree 在二叉樹中增加一行
Description:
Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.
Note that the root node is at depth 1.
The adding rule is:
Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
cur's original left subtree should be the left subtree of the new left subtree root.
cur's original right subtree should be the right subtree of the new right subtree root.
If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.
Example:
Example 1:
Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]
Example 2:
Input: root = [4,2,null,3,1], val = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]
Constraints:
The number of nodes in the tree is in the range [1, 10^4].
The depth of the tree is in the range [1, 10^4].
-100 <= Node.val <= 100
-10^5 <= val <= 10^5
1 <= depth <= the depth of tree + 1
題目描述:
給定一個二叉樹，根節(jié)點為第1層，深度為 1。在其第 d 層追加一行值為 v 的節(jié)點跟磨。
添加規(guī)則：給定一個深度值 d （正整數(shù)）间聊，針對深度為 d-1 層的每一非空節(jié)點 N吱晒，為 N 創(chuàng)建兩個值為 v 的左子樹和右子樹。
將 N 原先的左子樹沦童，連接為新節(jié)點 v 的左子樹仑濒；將 N 原先的右子樹，連接為新節(jié)點 v 的右子樹偷遗。
如果 d 的值為 1墩瞳，深度 d - 1 不存在，則創(chuàng)建一個新的根節(jié)點 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
注意:
輸入的深度值 d 的范圍是：[1，二叉樹最大深度 + 1]泵喘。
輸入的二叉樹至少有一個節(jié)點泪电。
思路:
- 遞歸
分為左子樹和右子樹遞歸 - BFS
按照層序遍歷到 depth 深度之后給隊列中的每一個節(jié)點加上 val 的節(jié)點
時間復(fù)雜度 O(n), 空間復(fù)雜度 O(n)
代碼:
C++:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution
{
public:
TreeNode* addOneRow(TreeNode* root, int val, int depth)
{
if (depth == 1) return new TreeNode(val, root, nullptr);
queue<TreeNode*> q{{root}};
while (--depth > 1)
{
int s = q.size();
while (s--)
{
auto cur = q.front();
q.pop();
if (cur -> left) q.emplace(cur -> left);
if (cur -> right) q.emplace(cur -> right);
}
}
while (!q.empty())
{
auto item = q.front();
item -> left = new TreeNode(val, item -> left, nullptr);
item -> right = new TreeNode(val, nullptr, item -> right);
q.pop();
}
return root;
}
};
Java:
/**
* 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 v, int d) {
if (d == 0 || d == 1) {
TreeNode t = new TreeNode(v);
if (d == 1) t.left = root;
else t.right = root;
return t;
}
if (root != null && d > 1) {
root.left = addOneRow(root.left, v, d > 2 ? d - 1 : 1);
root.right = addOneRow(root.right, v, d > 2 ? d - 1 : 0);
}
return root;
}
}
Python:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:
if depth == 1:
return TreeNode(val, root, None)
queue = [root]
while (depth := depth - 1) > 1:
s = len(queue) + 1
while (s := s - 1):
cur = queue.pop(0)
(cur.left and queue.append(cur.left)) or (cur.right and queue.append(cur.right))
for item in queue:
item.left, item.right = TreeNode(val, left=item.left), TreeNode(val, right=item.right)
return root
