差点忘记写了
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;
}