https://leetcode.com/problems/add-one-row-to-tree/?envType=daily-question&envId=2024-08-23
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 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, 104].
- The depth of the tree is in the range [1, 104].
- -100 <= Node.val <= 100
- -105 <= val <= 105
- 1 <= depth <= the depth of tree + 1
북적북적하지만~ 혼자 풀었다는 거
Binary Tree를 초기에 접하는 초심자가 풀이게 좋은 문제였다.
1. 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: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
if not root : return TreeNode(val)
elif depth == 1:
temp = TreeNode(val)
temp.left = root
return temp
q = deque()
q.append(root)
tree_lv = 0
while q:
tree_lv += 1
size = len(q)
if tree_lv == depth-1: # Get ya
for i in range(size):
curr = q.popleft()
templ = TreeNode(val)
templ.left = curr.left
curr.left = templ
tempr = TreeNode(val)
tempr.right = curr.right
curr.right = tempr
else:
for i in range(size):
curr = q.popleft()
if curr.left :
q.append(curr.left)
if curr.right:
q.append(curr.right)
return root
2. C
이번엔 Recursive하게 한 번 풀어보겠다. C는 Queue같은 container가 없으니;;
Recursion이 머리에 바로 바로 떠오르기엔 아직 경험치가 좀 부족한듯 하다..ㅠ
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void dfs_help(struct TreeNode* node, int d, int depth,int val);
struct TreeNode* addOneRow(struct TreeNode* root, int val, int depth) {
if(!root){
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
if(depth==1){
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = root;
newNode->right = NULL;
return newNode;
}
dfs_help(root,1,depth,val);
return root;
}
void dfs_help(struct TreeNode* node, int d, int depth,int val){
if(!node) return;
if(d==depth-1){
struct TreeNode* newNode_l = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode_l -> val = val;
struct TreeNode* newNode_r = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode_r -> val = val;
newNode_l->left = node->left;
newNode_l->right = NULL;
newNode_r->right = node->right;
newNode_r->left = NULL;
node->left = newNode_l;
node->right = newNode_r;
return;
}
dfs_help(node->left, d+1, depth, val);
dfs_help(node->right, d+1, depth, val);
};
3. C++
new 와 malloc의 차이를 알자.
그리고 C++과 달리 C에선 construct기능이 따로 없어서 instance initialize가 어렵다.
그래서 C에선 안 쓰는 left /right node들을 NULL로 일일히 설정해줘야 하지만, C++에선 initialize가 되어서 따로 언급이 없으면 val = 0 , left = nullptr 처럼 자동으로 설정이 가능하다.
/**
* 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:
void dfs_help(TreeNode* node, int val, int depth, int d){
if(!node) return;
if(d == depth-1){
TreeNode* newNode_l = new TreeNode(val);
TreeNode* newNode_r = new TreeNode(val);
newNode_l->left = node->left;
newNode_r->right = node->right;
node->left = newNode_l;
node->right = newNode_r;
return;
}
dfs_help(node->left,val,depth,d+1);
dfs_help(node->right,val,depth,d+1);
}
TreeNode* addOneRow(TreeNode* root, int val, int depth) {
if(depth==1){
TreeNode* newNode = new TreeNode(val);
newNode->left = root;
return newNode;
}
dfs_help(root,val,depth,1);
return root;
}
};