首页 > 试题广场 >

合并二叉树

[编程题]合并二叉树

热度指数：52884 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：
两颗二叉树是:
Tree 1

Tree 2

合并后的树为

数据范围：树上节点数量满足 $0 \le n \le 500$ ，树上节点的值一定在32位整型范围内。

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

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

输出

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

说明

如题面图

示例2

输入

{1},{}

输出

{1}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

你好，侦探先生

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param t1 TreeNode类
     * @param t2 TreeNode类
     * @return TreeNode类
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        } else if (t2 == null) {
            return t1;
        } else {
            t1.val = t1.val + t2.val;
            t1.left = mergeTrees(t1.left, t2.left);
            t1.right = mergeTrees(t1.right, t2.right);
            return t1;
        }
    }
}

编辑于 2024-03-28 10:19:16 回复(0)

Java

牛客839384289号

public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
    // write code here
    if(t1==null && t2==null){
        return null;
    }
    if(t1==null){
        return t2;
    }
    if(t2==null){
        return t1;
    }
    TreeNode root=new TreeNode(t1.val+t2.val);
    root.left=mergeTrees(t1.left ,t2.left);
    root.right=mergeTrees(t1.right ,t2.right);
    return root;
}

编辑于 2024-03-10 16:42:41 回复(0)

Java

dqxfz

public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {

if (t1 == null && t2 == null) {

return null;

}

if (t1 != null && t2 != null) {

t1.val += t2.val;

t1.left = mergeTrees(t1.left, t2.left);//合并左子树

t1.right = mergeTrees(t1.right, t2.right);//合并右子树

}

return t1 != null ? t1 : t2;

}

发表于 2023-09-20 21:12:09 回复(0)

Java

DDwu

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
       if(t1==null) return t2;
       if(t2==null) return t1;
       TreeNode t = new TreeNode (t1.val+t2.val);
       t.left = mergeTrees(t1.left,t2.left);
       t.right = mergeTrees(t1.right,t2.right);    
    return t;
    }
}

发表于 2023-07-24 21:12:51 回复(0)

Java

小杨yyy

import java.util.*;
//这个算法的空间复杂度难道不是o(n)吗，题目要求的是O(1)啊
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        //若只有一个节点返回另一个，两个都为null自然返回null
        if(t1==null){
            return t2;
        }
        if(t2==null){
            return t1;
        }
        //根左右的方式递归
        TreeNode head=new TreeNode(t1.val+t2.val);
        head.left=mergeTrees(t1.left,t2.left);
        head.right=mergeTrees(t1.right,t2.right);
        return head;
    }
   
}

发表于 2022-11-11 11:11:38 回复(0)

Java

dynamo1

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        // 把所加累加的数据放在t1中，如果t1分支节点不存在则将t2中的分支节点挂到t1上
        if(t1 == null && t2 == null) {
            return null;
        }else if (t1 == null) {
            return t2;
        }else if (t2 == null) {
            return t1;
        }
        t1.val = t1.val + t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        
        return t1;
    }

    
}

发表于 2022-11-08 23:36:45 回复(1)

Java

键盘都敲坏了.

递归合并两个树

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // 两个节点都为null，则没必要继续比较，直接返回null
        if(t1 == null && t2 == null)  return null;
        
        // 拿到两个节点的值之和
        int num = (t1 != null ? t1.val : 0) + (t2 != null ? t2.val : 0);
        
        
        if(t1 == null){
            // t1等于null时，创建一个对象 存储之和
            t1 = new TreeNode(num);
        }else{
            // 否则替换 val
            t1.val = num;
        }

        // 然后继续左子树递归遍历
        // 因为将t2 合并到 t1里，所以当递归拿到返回值以后，重新赋值给t1.left
        t1.left = mergeTrees(t1.left, t2 == null ? null : t2.left);
        
        // 然后继续右子树递归遍历
        // 因为将t2 合并到 t1里，所以当递归拿到返回值以后，重新赋值给t1.right
        t1.right = mergeTrees (t1.right, t2 == null ? null : t2.right);
        
        // 返回合并结果后的t1
        return t1;
    }
}

发表于 2022-11-05 12:02:19 回复(0)

Java

aklddnddkwndje

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        TreeNode t = null;
        int count = 0;
        if(t1!=null){
            count+=t1.val;
        }
        if(t2!=null){
            count+=t2.val;
        }
        if(count!=0){
            t = new TreeNode(count);
            add(t1.left,t2.left,t,true);
            add(t1.right,t2.right,t,false);
        }    
        return t;
    }
    
    
    public void add(TreeNode t1, TreeNode t2, TreeNode p, boolean flag){
        
        int count = 0;
        TreeNode t1l = null;
        TreeNode t1r = null;
        TreeNode t2l = null;
        TreeNode t2r = null;
        if(t1!=null){
            count+=t1.val;
            t1l = t1.left;
            t1r = t1.right;
        }
        if(t2!=null){
            count+=t2.val;
            t2l = t2.left;
            t2r = t2.right;
        }
        if(count!=0){
            TreeNode t = new TreeNode(count);
            if(flag){
                 p.left = t;
            }else{
                 p.right = t;
            }
            add(t1l,t2l,t,true);
            add(t1r,t2r,t,false);
        }    
    }
}

发表于 2022-09-06 22:49:04 回复(0)

Java

是小王吖🐅

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if(t1==null&&t2==null)
            return null;
        TreeNode node=new TreeNode(0);
        if(t1==null&&t2!=null){
            node.val=t2.val;
            node.left=mergeTrees(null,t2.left);
            node.right=mergeTrees(null,t2.right);
            return node;
        }
        if(t1!=null&&t2==null){
            node.val=t1.val;
            node.left=mergeTrees(t1.left,null);
            node.right=mergeTrees(t1.right,null);
            return node;
        }
        node.val=t1.val+t2.val;
        node.left=mergeTrees(t1.left,t2.left);
        node.right=mergeTrees(t1.right,t2.right);
        return node;
        
    }
}

发表于 2022-09-01 14:13:20 回复(0)

Java

牛客用户007

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param t1 TreeNode类
     * @param t2 TreeNode类
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if (t1 == null || t2 == null) return t1 == null ? t2 : t1;

        TreeNode head  = new TreeNode(t1.val + t2.val);

        head.left = mergeTrees(t1.left, t2.left);
        head.right = mergeTrees(t1.right, t2.right);

        return head;
    }
}

发表于 2022-08-26 10:41:19 回复(0)

Java

624huiguorou

合并二叉树

都合并到t1上。当t1为null，返回t2。当t2为null，返回t1。返回后都会被t1指针指向。

当t1和t2都不为null，则把t1和t2的值加上去给t1。

然后递归。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        //都合并到t1上
        //本身符合root，子树也符合
        if(t1 == null) return t2;
        if(t2 == null) return t1;
        //t1和t2都不为空
        t1.val = t1.val + t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
    

}

发表于 2022-07-24 20:06:00 回复(0)

Java

牛客517972170号

public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if(t1==null){
            return t2;
        }
        if(t2==null){
            return t1;
        }
        t1.val=t1.val+t2.val;
        t1.left=mergeTrees(t1.left,t2.left);
        t1.right=mergeTrees(t1.right,t2.right);
        return t1;
    }

发表于 2022-07-21 11:43:30 回复(0)

Java

wjp-niuke

public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
// write code here
if(t1==null) return t2;
if(t2==null) return t1;

t1.val=t1.val+t2.val;

TreeNode n1= mergeTrees(t1.left,t2.left);

TreeNode n2= mergeTrees(t1.right,t2.right);

t1.left=n1;
t1.right=n2;

return t1;

}

发表于 2022-07-20 09:06:33 回复(0)

Java

牛客62300892号

#递归解法，

可以把最后返回的结果用第一个二叉树代替，如果第一棵树为空的话，就让根节点指向右边的对应的二叉树的子节点。

public class Solution {

/**
*
* @param t1 TreeNode类
* @param t2 TreeNode类
* @return TreeNode类
*/
public TreeNode mergeTrees (TreeNode t1, TreeNode t2)
{
// write code here
if(t1!=null && t2!=null)
{
t1.val=t1.val+t2.val;
if(mergeTrees ( t1.left, t2.left)==t2.left)
t1.left=t2.left;
if(mergeTrees ( t1.right, t2.right)==t2.right)
t1.right=t2.right;


return t1;
}
else if(t1==null && t2!=null)

return t2;
else if (t2==null && t1!=null)
return t1;
else

return null;
}
}

发表于 2022-05-13 11:51:01 回复(0)

Java

毛豆来啦

递归

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        //如果两个节点都为空,则返回false
        if(t1 ==null && t2 ==null){
            return null;
        }else if(t1 != null && t2 == null){
            return t1;
        }else if(t1 == null && t2 != null){
            return t2;
        }else{
            t1.val = t1.val + t2.val;
            t1.left = mergeTrees(t1.left,t2.left);
            t1.right = mergeTrees(t1.right,t2.right);
            return t1;
        }
    }
}

发表于 2022-05-06 18:18:56 回复(0)

提交观点

问题信息

树

上传者：牛客332641号

难度：

44条回答 619收藏 4894浏览

通过挑战的用户

查看代码

随机昵称都有什...

2023-02-21 17:07:41
sp到手了的柯...

2022-11-03 22:25:34
牛客74843...

2022-10-11 09:32:40
牛客80848...

2022-09-16 17:12:13
想去北京的鳄鱼...

2022-09-16 16:44:44

合并二叉树

输入

输出

说明

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

递归

问题信息

热门推荐

通过挑战的用户

相关试题