why?
BM32 合并二叉树
- 题目
- 题解(3)
- 讨论(6)
- 排行
- 面经new
简单 通过率:65.89% 时间限制:1秒 空间限制:256M
知识点树
描述
已知两颗二叉树,将它们合并成一颗二叉树。合并规则是:都存在的结点,就将结点值加起来,否则空的位置就由另一个树的结点来代替。例如:
两颗二叉树是:
Tree 1
Tree 2
合并后的树为
数据范围:树上节点数量满足 0≤𝑛≤5000≤n≤500,树上节点的值一定在32位整型范围内。
进阶:空间复杂度 𝑂(1)O(1) ,时间复杂度 𝑂(𝑛)O(n)
static struct TreeNode* pre,*final;
bool visit(struct TreeNode* t1, struct TreeNode* t2){
if(t2==NULL){//之后都没有节点返回
return true;
}
if(t1!=NULL&&t2!=NULL){
t1->val+=t2->val;//t1,t2对应位置都存在节点
printf("%d ",t1->val);
}
if(t1==NULL){//t1没有,t2有,给t1续上,然后返回
if(pre->left==NULL&&final->left==t2)//匹配父节点
//if(pre->left==NULL)
pre->left=t2;
else
pre->right=t2;
return true;
}
pre=t1;final=t2;
visit(t1->left,t2->left);
visit(t1->right,t2->right);
return true;
}
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) {
// write code here
if(t1==NULL)//t1为空,返回t2
return t2;
if(t2==NULL)//t2为空,返回t1
return t1;
pre=NULL;final=NULL;
visit(t1,t2);
return t1;
}