当前位置:网站首页>Leetcode brush questions: binary tree 19 (merge binary tree)
Leetcode brush questions: binary tree 19 (merge binary tree)
2022-07-07 12:47:00 【Taotao can't learn English】
617. Merge binary tree
Given two binary trees , Imagine when you overlay one of them on the other , Some nodes of two binary trees will overlap .
You need to merge them into a new binary tree . The rule for merging is if two nodes overlap , Then add their values as the new values after node merging , Otherwise, no NULL The node of will be the node of the new binary tree directly .
Example 1:
Be careful : The merge must start at the root of both trees .
Based on one of the trees , Recursively traverse two trees at the same time , Each time, judge whether the current node exists in the non benchmark tree , Then add , non-existent , Then skip , The current node does not exist , Exist in non benchmark tree , Then add this node with the passed parent node , Remember to mark which tree it is .
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;
}
// Based on the first tree
if (root1 != null && root2 != null) {
root1.val = root1.val + root2.val;
}
if (root1 == null && root2 != null) {
// If 1 No, ,2 Yes
if (isLeft) {
parent.left = root2;
return;
} else {
parent.right = root2;
return;
}
}
// If 1 Yes , 2 No, Do not change
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]")
);
}
}
Let's take a look at the big guy's code
// recursive
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;
}
边栏推荐
猜你喜欢
BGP third experiment report
对话PPIO联合创始人王闻宇:整合边缘算力资源,开拓更多音视频服务场景
OSPF exercise Report
Static comprehensive experiment
Cookie
Day-19 IO stream
Master公式。(用于计算递归的时间复杂度。)
Dialogue with Wang Wenyu, co-founder of ppio: integrate edge computing resources and explore more audio and video service scenarios
Charles: four ways to modify the input parameters or return results of the interface
ICLR 2022 | pre training language model based on anti self attention mechanism
随机推荐
The IDM server response shows that you do not have permission to download the solution tutorial
普乐蛙小型5d电影设备|5d电影动感电影体验馆|VR景区影院设备
2022聚合工艺考试题模拟考试题库及在线模拟考试
Object. Simple implementation of assign()
How much does it cost to develop a small program mall?
Image pixel read / write operation
Solutions to cross domain problems
leetcode刷题:二叉树27(删除二叉搜索树中的节点)
通讯协议设计与实现
BGP actual network configuration
leetcode刷题:二叉树25(二叉搜索树的最近公共祖先)
Cryptography series: detailed explanation of online certificate status protocol OCSP
图形对象的创建与赋值
Visual stdio 2017 about the environment configuration of opencv4.1
2022广东省安全员A证第三批(主要负责人)考试练习题及模拟考试
Vxlan 静态集中网关
[statistical learning methods] learning notes - Chapter 4: naive Bayesian method
[statistical learning method] learning notes - support vector machine (I)
【统计学习方法】学习笔记——支持向量机(下)
Aike AI frontier promotion (7.7)