当前位置:网站首页>leetcode刷题:二叉树19(合并二叉树)
leetcode刷题:二叉树19(合并二叉树)
2022-07-07 10:30:00 【涛涛英语学不进去】
617.合并二叉树
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
注意: 合并必须从两个树的根节点开始。
以其中一棵树为基准,递归同时遍历两棵树,每次判断当前结点在非基准树里若存在,则相加,不存在,则跳过,当前结点不存在,在非基准树里存在,则用传来的父结点添加这个结点,记得标记一下是哪棵树。
package com.programmercarl.tree;
import com.programmercarl.util.GenerateTreeNode;
import java.util.ArrayDeque;
import java.util.Deque;
/** * @ClassName MergeTrees * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 18:02 * @Version 1.0 **/
public class MergeTrees {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 != null) {
return root2;
}
if (root1 != null && root2 == null) {
return root1;
}
if (root1 == null && root2 == null) {
return null;
}
merge(root1, root2, false,null);
return root1;
}
public void merge(TreeNode root1, TreeNode root2, boolean isLeft,TreeNode parent) {
if (root1 == null && root2 == null) {
return;
}
// 以第一棵树为基准
if (root1 != null && root2 != null) {
root1.val = root1.val + root2.val;
}
if (root1 == null && root2 != null) {
//如果 1 没有,2 有
if (isLeft) {
parent.left = root2;
return;
} else {
parent.right = root2;
return;
}
}
//如果 1 有 , 2 没有 不做改变
if (root1 != null && root2 == null) {
return;
}
merge(root1.left, root2.left, true,root1);
merge(root1.right, root2.right, false,root1);
}
public static void main(String[] args) {
new MergeTrees().mergeTrees(
GenerateTreeNode.generateTreeNode("[9,-1,null,-2,0,-4,null,null,8,-5,-3,6,null,null,null,null,null,null,7]")
,
GenerateTreeNode.generateTreeNode("[-1,-2,0,null,null,null,8,6,null,null,7]")
);
}
}
来看看大佬的代码
// 递归
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
TreeNode newRoot = new TreeNode(root1.val + root2.val);
newRoot.left = mergeTrees(root1.left,root2.left);
newRoot.right = mergeTrees(root1.right,root2.right);
return newRoot;
}
边栏推荐
- Configure an encrypted web server
- (待会删)yyds,付费搞来的学术资源,请低调使用!
- Airserver automatically receives multi screen projection or cross device projection
- @What happens if bean and @component are used on the same class?
- PowerShell cs-utf-16le code goes online
- Routing strategy of multi-point republication [Huawei]
- On valuation model (II): PE index II - PE band
- 普乐蛙小型5d电影设备|5d电影动感电影体验馆|VR景区影院设备
- ES底层原理之倒排索引
- ENSP MPLS layer 3 dedicated line
猜你喜欢
30. Feed shot named entity recognition with self describing networks reading notes
SQL Lab (32~35) contains the principle understanding and precautions of wide byte injection (continuously updated later)
SQL lab 11~20 summary (subsequent continuous update) contains the solution that Firefox can't catch local packages after 18 levels
[statistical learning methods] learning notes - improvement methods
<No. 9> 1805. Number of different integers in the string (simple)
On valuation model (II): PE index II - PE band
金融数据获取(三)当爬虫遇上要鼠标滚轮滚动才会刷新数据的网页(保姆级教程)
Attack and defense world - PWN learning notes
EPP+DIS学习之路(2)——Blink!闪烁!
idm服务器响应显示您没有权限下载解决教程
随机推荐
Xiaohongshu microservice framework and governance and other cloud native business architecture evolution cases
Decrypt gd32 MCU product family, how to choose the development board?
When OSPF specifies that the connection type is P2P, it enables devices on both ends that are not in the same subnet to Ping each other
Object. Simple implementation of assign()
小红书微服务框架及治理等云原生业务架构演进案例
On valuation model (II): PE index II - PE band
30. Few-shot Named Entity Recognition with Self-describing Networks 阅读笔记
idea 2021中文乱码
SQL blind injection (WEB penetration)
Processing strategy of message queue message loss and repeated message sending
[pytorch practice] image description -- let neural network read pictures and tell stories
SQL Lab (32~35) contains the principle understanding and precautions of wide byte injection (continuously updated later)
wallys/Qualcomm IPQ8072A networking SBC supports dual 10GbE, WiFi 6
Tutorial on the principle and application of database system (011) -- relational database
File upload vulnerability - upload labs (1~2)
Completion report of communication software development and Application
Experiment with a web server that configures its own content
Unity 贴图自动匹配材质工具 贴图自动添加到材质球工具 材质球匹配贴图工具 Substance Painter制作的贴图自动匹配材质球工具
【PyTorch实战】用RNN写诗
SQL Lab (46~53) (continuous update later) order by injection