差點忘記寫了
623. Add One Row to Tree
思路：
沒什麼好講的
用BFS或是遞迴都可以看你爽就好
我是用遞迴
要在深度為depth地方插入節點
那就是要停在depth-1的深度，並且建立兩個新節點
新的左子節點的左子節點為母節點的左子節點
新的右子節點的右子節點為母節點的右子節點
記得當node==NULL || 現在的深度比depth-1還深，要跳出
C CODE:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void dfs(int depth,int nowdepth,struct TreeNode * node,int val){
if (depth<nowdepth || node==NULL){
return ;
}
if (depth==nowdepth){
struct TreeNode* newright=(struct TreeNode *)calloc(1,sizeof(struct
TreeNode));
struct TreeNode* newleft=(struct TreeNode *)calloc(1,sizeof(struct
TreeNode));
newright->val=val;
newleft->val=val;
newright->right=node->right;
newleft->left=node->left;
node->right=newright;
node->left=newleft;
return ;
}else{
dfs(depth,nowdepth+1,node->right,val);
dfs(depth,nowdepth+1,node->left,val);
}
}
struct TreeNode* addOneRow(struct TreeNode* root, int val, int depth) {
if (depth==1){
struct TreeNode *ans=(struct TreeNode *)calloc(1,sizeof(struct
TreeNode));
ans->val=val;
ans->left=root;
return ans;
}
dfs(depth-1,1,root,val);
return root;
}