首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >24 Merge Two Binary Trees

24 Merge Two Binary Trees

作者头像
devi
发布于 2021-08-18 08:02:11
发布于 2021-08-18 08:02:11
22900
代码可运行
举报
文章被收录于专栏:搬砖记录搬砖记录
运行总次数:0
代码可运行

题目

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Note: The merging process must start from the root nodes of both trees.

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        
    }
}

分析

题意:给两棵二叉树,将其每个节点相加。

难点:如何同时遍历两棵树的左右子节点

思路一:

  1. 遍历的结束条件是两棵树的当前节点都为空
  2. 新树当前节点值 = (t1.val==null?0:t1.val)+(t2.val==null?0:t2.val)
  3. 新树的左子树 = 递归( 两颗树的左子树)
  4. 新树的右子树 = 递归(两棵树的右子树)

思路二:

  1. 将第一课树作为新树
  2. 如果当前树为空,则返回另一棵树的节点值
  3. 把第二棵树的节点值加到第一棵树的节点上
  4. 第一棵树(新树)的左子树 = 递归( 两颗树的左子树)
  5. 第一棵树(新树)的右子树 = 递归(两棵树的右子树)

解答

法一:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null && t2==null){
            return null;
        }
        int x = (t1==null?0:t1.val) +(t2==null?0:t2.val);
        TreeNode newNode = new TreeNode(x);
        newNode.left = mergeTrees(t1==null?null:t1.left,t2==null?null:t2.left);
        newNode.right = mergeTrees(t1==null?null:t1.right,t2==null?null:t2.right);
        return newNode;
        
    }
}

法二:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        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;
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/02/15 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【Tree】617. Merge Two Binary Trees
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
echobingo
2019/05/15
2910
LeetCode 344 Merge Two Binary Trees
基本思路是将两棵树, 合并到左树上, 基本规则是只有当 tree1 和 tree2 相同位置的节点都不为空时, 才能进行相加操作, 当 tree1 为空时, 把 tree2 的节点嫁接过来, 当 tree2 为空时, 保留 tree1 即可. 以此类推, 把每个节点都看成根节点即可.
一份执着✘
2019/12/30
3820
LeetCode-617-合并二叉树
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
benym
2022/07/14
1600
二叉树——617. 合并二叉树
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。
向着百万年薪努力的小赵
2022/12/02
4280
二叉树——617. 合并二叉树
leetcode-617. 合并二叉树
  这道题首先对传进来的两个树节点进行判空,若 t1 的值为空,则返回 t2 的值,若 t2 的值为空则直接返回 t1 的值。若两个均不为空,则两个进行相加,由于传进来的是两个根节点,因此新的树的根节点即为这两个值的和,接下来就是要把两颗二叉树对应位置的值进行相加作为新的二叉树对应位置的值,用 mergeTrees 方法对整棵树的所有左子树完成以上相加的操作,同理再对所有右子树进行对应相加的操作,最终一颗新的符合题意的二叉树就生成了。
灰太狼学Java
2022/06/17
1450
leetcode-617. 合并二叉树
15 道二叉树手写算法题(三)
Leetcode 572. Subtree of Another Tree (Easy)
乔戈里
2019/04/24
5610
15 道二叉树手写算法题(三)
2021-12-20:合并二叉树。 给定两个二叉树,想象当你将它
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
福大大架构师每日一题
2021/12/20
3310
LintCode 子树题目分析代码
有两个不同大小的二进制树: T1有上百万的节点; T2有好几百的节点。请设计一种算法,判定 T2是否为 T1的子树。
desperate633
2018/08/22
3180
LintCode 子树题目分析代码
Golang Leetcode 617. Merge Two Binary Trees.go
更多内容请移步我的repo:https://github.com/anakin/golang-leetcode
anakinsun
2019/04/22
4700
LeetCode - 合并二叉树
LeetCode第617题,难度为简单,最近的这些题目,都是今年4月刚开始继续刷算法的时候写的,全是简单,用于加强信心。
晓痴
2019/07/24
4180
LeetCode - 合并二叉树
【算法总结】五道常见的算法-二叉树
前段时间,写了面试必备的一系列文章,反应还不错。有一些读者反馈说,能不能整理一些面试常见的算法。前段时间,我恰好总结了 LeetCode 常见的面试算法题目。
程序员徐公
2022/01/20
1.1K0
【算法总结】五道常见的算法-二叉树
【Leetcode】【python】Hamming Distance, Merge Two Binary Trees
两个整数的汉明距离是指其二进制不相等的位的个数。 给定两个整数x和y,计算汉明距离。 注意: 0 ≤ x, y < 2^31.
蛮三刀酱
2019/03/26
4100
LeetCode 617. 合并二叉树
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
Michael阿明
2022/11/26
2870
LeetCode 617. 合并二叉树
LeetCode,合并二叉树
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
微客鸟窝
2021/08/18
4060
LeetCode,合并二叉树
另一个树的子树
给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
零式的天空
2022/03/21
2350
LeetCode 617. 合并二叉树
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
freesan44
2020/03/20
3130
leetCode167|合并二叉树
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
码农王同学
2021/01/15
3000
LeetCode,Go实现对称二叉树的判别
这样就形成了递归问题,对于两个子树,需要判断子树的子树是否对称。注意临界点:如果所给根节点,为空,那么是对称。
微客鸟窝
2021/08/18
2670
LeetCode,Go实现对称二叉树的判别
天天算法 LeetCode-101-对称二叉树
https://leetcode-cn.com/problems/symmetric-tree/
灵魂画师牧码
2019/06/26
3710
天天算法 LeetCode-101-对称二叉树
给定一个二叉树,检查它是否是镜像对称的。
判断二叉树是否镜像对称==>(左子树的右节点等于右子树的左节点)&&(右子树的右节点等于左子树的左节点)
小雨的分享社区
2022/10/26
6550
相关推荐
【Tree】617. Merge Two Binary Trees
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档