当前位置:网站首页>Leetcode brush questions - 543. Diameter of binary trees, 617. Merging binary trees (recursive solution)
Leetcode brush questions - 543. Diameter of binary trees, 617. Merging binary trees (recursive solution)
2022-08-04 11:13:00 【lonelyMangoo】
递归
To solve these two problems, I would like to first understand the idea of recursion,There are three elements to solving recursive problems:
- 方法参数和返回值
- 方法参数:There are two cases for method parameters
- If it is related to the previous,Then you have to set it as a global variable
例如刷题中的538题,就会出问题,As a result, the value passed in is not the latest,下面的543the same question. - If it doesn't matter before,That is to say, it only works on the current layer,即局部的,It is passed through the method body
- If it is related to the previous,Then you have to set it as a global variable
- 返回值
When you need to use the return value,设置返回值,The following two questions will be required,
而上面提到的刷题中的538题,已经使用sumThe values I need are logged,No return value operation is required.另外,Generally judged with return value,有false直接返回了.
- 终止条件
It's where you need to be clear,When to stop and when to end. - 函数体
Operations on nodes and data
下面的题目,I will go through the above three steps to analyze
543. 二叉树的直径
543. 二叉树的直径
这道题翻译一下,Find the largest of the sum of the heights of the left and right subtrees of each node.
Why grab every node,Because I did it with hierarchical traversal at first,I thought it must start from the follow node,这个想法是错的,举个例子,The height of the root's right subtree is 1,The left subtree is two subtrees of the same height,高度都为10.
代码:
//It is written outside because this is a global variable,Find the global largest.
int ans;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return ans;
}
//The return value is set because it is needed to find the height
private int depth(TreeNode root){
//结束条件
if(root == null){
return 0;
}
//方法体
// Recursively find the height of the left and right subtrees of the current node
int leftDepth = depth(root.left);
int rightDepth = depth(root.right);
ans = Math.max(ans,leftDepth+rightDepth);
//返回当前子树的高度
return Math.max(leftDepth,rightDepth)+1;
}
617. 合并二叉树
617. 合并二叉树
题目很好理解,思路,Pick up new ones
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
return build(root1, root2);
}
//先序遍历.
//The return value is set because it is needed to build a tree
public static TreeNode build(TreeNode root1, TreeNode root2){
//终止条件
//叶子结点,直接返回
if(root1==null && root2==null) return null;
//And wool scallops,可冲
if(root1!=null && root2==null) return root1;
if(root1==null && root2!=null) return root2;
//The overlapping part of the left and right subtrees,需要叠加,
TreeNode node = new TreeNode(root1.val + root2.val);
//建树,Here you can see the return value that needs to be used.
node.left=build(root1.left, root2.left);
node.right=build(root1.right,root2.right);
return node;
}
边栏推荐
猜你喜欢
【Idea series】idea configuration
Leetcode brush questions - binary search tree related topics (98. Verify binary search tree, 235. The nearest common ancestor of binary search tree, 1038. From binary search tree to bigger sum tree, 5
mae,mse,rmse分别利用sklearn和numpy实现
Heap Sort
解析treeSet集合进行自定义类的排序
第二批养老理财试点产品发行 一小时销售20亿元
CVPR 2022 | 从人体网格预测骨架,是真正的生理学骨架!
热成像测温的原理是什么呢?你知道吗?
深度强化学习与APS的一些感想
iMeta | German National Cancer Center Gu Zuguang published a complex heatmap visualization method
随机推荐
Xilinx VIVADO 中 DDR3(Naive)的使用(2)读写设计
数据化管理洞悉零售及电子商务运营——零售密码
遍历Map的四种方法
cubemx stm32 afm3000 module gas flow sensor driver code
北京大学,新迎3位副校长!其中一人为中科院院士!
The use of DDR3 (Naive) in Xilinx VIVADO (3) simulation test
Graphical Hands-on Tutorial--ESP32 One-Key Network Configuration (Smartconfig, Airkiss)
Leetcode - using sequence traversal features first completed 114. The binary tree to the list
使用.NET简单实现一个Redis的高性能克隆版(二)
Mysql高级篇学习总结13:多表连接查询语句优化方法(带join语句)
Zikko launches new Thunderbolt 4 docking station with both HDMI2.1 and 2.5GbE
Oracle中对临时表空间执行shrink操作
【LeetCode】899.有序队列
【LeetCode】98.验证二叉搜索树
第二批养老理财试点产品发行 一小时销售20亿元
【虹科案例】基于3D相机组装家具
datax oracle to oracle incremental synchronization
AWS Lambda相关概念与实现思路
【Idea series】idea configuration
SkiaSharp 之 WPF 自绘 粒子花园(案例版)