首页 > 试题广场 >

合并二叉树

[编程题]合并二叉树

热度指数：60611 时间限制：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

牛客348570162号

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

发表于 2024-08-26 22:55:48 回复(0)

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) {
        // write code here

        // 根据左程云老师讲的【二叉树递归套路】，先弄明白三件事
        // 1.我要干什么：
        //        令root.left   ->   【左子树】的【完整形态的根节点】
        //        令root.right  ->   【右子树】的【完整形态的根节点】

        // 2.我需要什么信息：
        //      综上所述，我需要左右子树的【完整形态的根节点】

        // 3.我如何利用两个子树的信息加工出来我的信息：
        //      将root.left和root.right分别指向了正确的完整子树根节点后，【root】本身就是这个子树的完整根节点

        return process(t1, t2);
    }

    // 递归序遍历二叉树函数 - 返回当前子树下的merge后的完整根节点
    public TreeNode process(TreeNode t1, TreeNode t2) {
        // 递归出口
        if (t2 == null) {
            // t2空，说明没有什么可修改或补充t1的了，因此没有继续下去的必要了
            return t1;
        }
        if (t1 == null) {
            // t1空，而t2非空，返回t2作为上一层的子树，相当于补充t1了
            // 踩坑！这里如果采用的是“public 【void】 process(TreeNode t1, TreeNode t2)”就会出问题
            // 因为t1是null，如果令t1 = t2，那么这个t2【并不能】作为子树返回给上一层的t1
            // 所以这里采取将TreeNode对象返回，由上一层亲自将左右结点指向它，保证没问题
            return t2;
        }
        // t1非空，且t2非空
        t1.val += t2.val;

        // 令t1的左右指针分别指向左右两个完整子树的根节点
        t1.left = process(t1.left, t2.left);
        t1.right = process(t1.right, t2.right);
        return t1;
    }
}

发表于 2024-07-29 22:24:53 回复(0)

Java

sevenkeep

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;

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

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

        return t1;
    }
}

发表于 2024-06-21 17:21:13 回复(0)

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)

提交观点

问题信息

树

上传者：牛客332641号

难度：

47条回答 741收藏 5892浏览

通过挑战的用户

查看代码

随机昵称都有什...

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，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题