力扣题617合并二叉树
发布日期:2022-03-04 11:48:21
浏览次数:5
分类:技术文章
本文共 1855 字,大约阅读时间需要 6 分钟。
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出: 合并后的树: 3 / \ 4 5 / \ \ 5 4 7 注意: 合并必须从两个树的根节点开始。1.深度优先遍历。每个对应的节点进行相加,然后分情况进行递归讨论。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { TreeNode node = new TreeNode(); if (root1 == null && root2 == null) {//如果两个节点都是null return null; } else if (root1 == null) {//root1为null,root2不为null node.val = root2.val; node.left = mergeTrees(null,root2.left); node.right = mergeTrees(null,root2.right); } else if (root2 == null) {//root2为null,root1不为null node.val = root1.val; node.left = mergeTrees(root1.left,null); node.right = mergeTrees(root1.right,null); } else {//root1、root2不为null node.val = root1.val + root2.val; node.left = mergeTrees(root1.left,root2.left); node.right = mergeTrees(root1.right,root2.right); } return node; }}
可以优化:
class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) { return root2; } if (root2 == null) { return root1; } TreeNode node = new TreeNode(root1.val + root2.val); node.left = mergeTrees(root1.left,root2.left); node.right = mergeTrees(root1.right,root2.right); return node; }}
题源:
转载地址:https://blog.csdn.net/xxyneymar/article/details/122316184 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年03月29日 20时58分54秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
HDU - Robberies(01背包)
2019-04-28
HDU - 最大报销额(01背包|贪心)
2019-04-28
HDU - Coins(完全背包)
2019-04-28
JXFCZX — 砝码称重1(DFS+背包)
2019-04-28
JXFCZX — 质数和分解(完全背包)
2019-04-28
JXFCZX — 花店橱窗(动态规划)
2019-04-28
JXFCZX — 逃亡的准备(多重背包)
2019-04-28
JXFCZX — 庆功会(多重背包)
2019-04-28
AcWing - 扩展欧几里得算法(扩欧)
2019-04-28
AcWing - 高斯消元解线性方程组(高斯消元)
2019-04-28
AcWing - 求组合数 I(递推)
2019-04-28
AcWing - 求组合数 II(预处理&逆元)
2019-04-28
AcWing - 求组合数 III(lucas&逆元)
2019-04-28
AcWing - 求组合数 IV(分解质因数)
2019-04-28
AcWing - 满足条件的01序列(组合数学&卡特兰数)
2019-04-28
AcWing - 快速排序(快排)
2019-04-28
AcWing - 归并排序(归排)
2019-04-28
AcWing - 数的范围(二分)
2019-04-28
AcWing - 数的三次方根(二分)
2019-04-28
AcWing - 高精度加法(大数加法)
2019-04-28