LETCode 623 : 1行をツリー[ソリューション]に追加する
難易度:中
ジャンプします
問題声明
Given the root of a binary tree, then value v
and depth d
, you need to add a row of nodes with value v
at the given depth d
. The root node is at depth 1.
The adding rule is: given a positive integer depth d
, for each NOT null tree nodes N
in depth d-1
, create two tree nodes with value v
as N's
left subtree root and right subtree root. And N's
original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d
is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.
Example 1:
Input:
A binary tree as following:
4
/ \
2 6
/ \ /
3 1 5
v = 1
d = 2
Output:
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5
Example 2:
Input:
A binary tree as following:
4
/
2
/ \
3 1
v = 1
d = 3
Output:
4
/
2
/ \
1 1
/ \
3 1
Note:
- The given d is in the range [1, maximum depth of the given tree + 1].
- The given binary tree has at least one tree node.
解説
So the problem is quite simple, You are given a non-empty binary tree and a value v
which needs to be inserted as a child at depth d
for all non-empty parent nodes. The new node will be at both left and right edge of the parent. The child nodes/subtree of the parent need to be set as the child of the newly created node with the same direction left/right. This should be clear with the given examples.
解決策
We are going to do only the below things:
- If
depth=1
i.e. we need to add the value at root, then we just need to create a new node with valuev
and make the currentroot
its left child and return the pointer to the new node. - We need to traverse the tree in both directions (left/right) till we reach the depth
d-1
. Let's say we are at the nodeparent
, this is the node below which the new nodes need to be added. - Now we need to create a new node for the left subtree of
parent
so this new node's left pointer will point to the left subtree ofparent
and then we'll makeparent
's left pointer point to the new node. That's how we have added a node between theparent
and left subtree. - Same needs to be done for the right subtree.
As we'll be going down to the tree, we can call it DFS(Depth First Search) based on recursion. So Time Complexity: of this solution may go to O(n)
as we might need to add the nodes below the leaf. As recursion uses stack so the Space Complexity: can be O(n)
in the worst case.
実装
C++ Code:
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
// If need to add the row on root
if(d==1){
// Just create a new node with value v
// and current root as left child
TreeNode *ptr = new TreeNode(v, root, nullptr);
return ptr;
}
// Traverse down to the parent node at depth d-1
// to add row at depth d(>1)
addRow(root, v, d-1);
// Return same pointer root with modified tree
return root;
}
// Function to traverse down to the depth d-1 and add row
void addRow(TreeNode* parent, int v, int dep){
// If node is NULL the do nothing
if(!parent)
return;
// If we have reached depth d-1 i.e. dep=1
if(dep==1){
TreeNode *temp;
// Store left ptr
temp = parent->left;
// Replace left ptr with new node with value v
parent->left = new TreeNode(v);
// Set stored left pointer as new node's left ptr
parent->left->left = temp;
// Store right ptr
temp = parent->right;
// Replace right ptr with new node with value v
parent->right = new TreeNode(v);
// Set stored right pointer as new node's right ptr
parent->right->right = temp;
}
// Else go deeper
else{
addRow(parent->left, v, dep-1);
addRow(parent->right, v, dep-1);
}
}
};
Runnable C++ Code:
Reference
この問題について(LETCode 623 : 1行をツリー[ソリューション]に追加する), 我々は、より多くの情報をここで見つけました https://dev.to/shivams136/leetcode-623-add-one-row-to-tree-solution-dmfテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol