首页 > 试题广场 >

合并二叉树

[编程题]合并二叉树
  • 热度指数：59244 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：
两颗二叉树是:
                                                                    Tree 1


                                                                        Tree 2

                                                                    合并后的树为
数据范围：树上节点数量满足 ，树上节点的值一定在32位整型范围内。
进阶：空间复杂度 ，时间复杂度
示例1

输入

{1,3,2,5},{2,1,3,#,4,#,7}

输出

{3,4,5,5,4,#,7}

说明

如题面图
示例2

输入

{1},{}

输出

{1}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C
求offer的她很讲文明头像 求offer的她很讲文明
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param t1 TreeNode类
 * @param t2 TreeNode类
 * @return TreeNode类
 */

#include <stdio.h>

struct TreeNode * Depth_Add(struct TreeNode * t)
{
    if(t == NULL)
    {
        return NULL;
    }
    struct TreeNode * pnew = malloc(sizeof(struct TreeNode));
    pnew->val = t->val;
    pnew->right = NULL;
    pnew->left = NULL;
    printf("1val = %d\n", t->val);

    pnew->right = Depth_Add(t->right);
    pnew->left = Depth_Add(t->left);

    return pnew;
}

struct TreeNode * pre_printAdd(struct TreeNode * t1, struct TreeNode * t2)
{
    if(!t1 && !t2)
    {
        return NULL;
    }

    if(t1 != NULL && t2 == NULL)
    {
        struct TreeNode * pnew = malloc(sizeof(struct TreeNode));
        pnew->val = t1->val;
        pnew->left = Depth_Add(t1->left);
        pnew->right = Depth_Add(t1->right);
        return pnew;
    }
    if(t1 == NULL && t2 != NULL)
    {
        struct TreeNode * pnew = malloc(sizeof(struct TreeNode));
        pnew->val = t2->val;
        pnew->left = Depth_Add(t2->left);
        pnew->right = Depth_Add(t2->right);
        return pnew;
    }

    struct TreeNode * pnew = malloc(sizeof(struct TreeNode));

    pnew->val = t1->val + t2->val;
    printf("2val = %d\n", pnew->val);
    pnew->right = pre_printAdd(t1->right, t2->right);
    pnew->left = pre_printAdd(t1->left, t2->left);
    return pnew;
}

struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) {
    // write code here

    if(!t1 || !t2)
    {
        return t1 ? t1 : t2;        
    }
    struct TreeNode * newtree = pre_printAdd(t1, t2);

    return newtree;
} 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param t1 TreeNode类 
 * @param t2 TreeNode类 
 * @return TreeNode类
 */

#include <stdio.h>

struct TreeNode * Depth_Add(struct TreeNode * t)
{
    if(t == NULL)
    {
        return NULL;
    }
    struct TreeNode * pnew = malloc(sizeof(struct TreeNode));
    pnew->val = t->val;
    pnew->right = NULL;
    pnew->left = NULL;
    printf("1val = %d\n", t->val);

    pnew->right = Depth_Add(t->right);
    pnew->left = Depth_Add(t->left);

    return pnew;
}


struct TreeNode * pre_printAdd(struct TreeNode * t1, struct TreeNode * t2)
{
    if(!t1 && !t2)
    {
        return NULL;
    }

    if(t1 != NULL && t2 == NULL)
    {
        struct TreeNode * pnew = malloc(sizeof(struct TreeNode));
        pnew->val = t1->val;
        pnew->left = Depth_Add(t1->left);
        pnew->right = Depth_Add(t1->right);
        return pnew;
    }
    if(t1 == NULL && t2 != NULL)
    {
        struct TreeNode * pnew = malloc(sizeof(struct TreeNode));
        pnew->val = t2->val;
        pnew->left = Depth_Add(t2->left);
        pnew->right = Depth_Add(t2->right);
        return pnew;
    }

    struct TreeNode * pnew = malloc(sizeof(struct TreeNode));

    pnew->val = t1->val + t2->val;
    printf("2val = %d\n", pnew->val);
    pnew->right = pre_printAdd(t1->right, t2->right);
    pnew->left = pre_printAdd(t1->left, t2->left);
    return pnew;
}

struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) {
    // write code here

    if(!t1 || !t2)
    {
        return t1 ? t1 : t2;        
    }
    struct TreeNode * newtree = pre_printAdd(t1, t2);

    return newtree;
}

发表于 2024-05-08 21:27:55 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) {
    struct TreeNode *RootTreeNode;
    if(t1==NULL) 
        return t2;
    if(t2==NULL)
        return t1;
    
    RootTreeNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    RootTreeNode->val = t1->val+t2->val;
    RootTreeNode->left = mergeTrees(t1->left, t2->left);
    RootTreeNode->right = mergeTrees(t1->right, t2->right);

    return RootTreeNode;
}

编辑于 2024-03-16 16:59:00 回复(0)
C
陈让然头像 陈让然
    
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) 
{
    // write code here
    //若t1不存在或都不存在,返回t2
    if(!t1||!t2)
    {
        return t1?t1:t2;
    }
    //相同位置结点值相加
    t1->val+=t2->val;
    //遍历左子树
    t1->left=mergeTrees(t1->left,t2->left);
    //遍历右子树
    t1->right=mergeTrees(t1->right,t2->right);
    //t2移入t1
    return t1;
}


发表于 2023-11-17 17:05:14 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param t1 TreeNode类
 * @param t2 TreeNode类
 * @return TreeNode类
 */
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 )
{
    // write code here
    if(t1&&t2)
    {
        t1->val=t1->val+t2->val;
        if(t1->left&&t2->left)
        {
            mergeTrees(t1->left,t2->left);
        }
        else if(!t1->left&&t2->left)
        {
            t1->left=t2->left;
        }
        if(t1->right&&t2->right)
        {
            mergeTrees(t1->right,t2->right);
        }
        else if(!t1->right&&t2->right)
        {
            t1->right=t2->right;
        }
    }
    if(t1)
    {
        return t1;
    }
    else
    {
        return t2;
    }
}
发表于 2023-07-09 10:31:26 回复(0)
C
木弎头像 木弎 
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) {
    // write code here
    if(!t1||!t2) return t1?t1:t2;//比较那棵二叉树的子树不为空
    t1->val+=t2->val;//存在的结点的值相加
    t1->left=mergeTrees(t1->left,t2->left);//接收返回更长的左子树
    t1->right=mergeTrees(t1->right,t2->right);//接收返回更长的右子树
    return t1;
}

发表于 2022-11-26 16:43:24 回复(0)
C
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) {
  if (!t1 || !t2) return t1 ? t1 : t2;
  t1->val += t2->val;
  t1->left  = mergeTrees(t1->left,  t2->left);
  t1->right = mergeTrees(t1->right, t2->right);
  return t1;
}

发表于 2021-07-24 09:22:53 回复(0)
提交观点

问题信息

树
上传者：牛客332641号
难度：
6条回答 5679浏览

热门推荐

通过挑战的用户

查看代码

相关试题

合并二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号