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;

}