当前位置:网站首页>leetcode刷题:二叉树16(路径总和)
leetcode刷题:二叉树16(路径总和)
2022-07-05 19:52:00 【涛涛英语学不进去】
112. 路径总和
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
递归遍历,如果只有左子树,则只计算左子树,如果只有右子树,则只计算右子树,遇到空节点则开始比较,把递归结果 或 运算 即可。
package com.programmercarl.tree;
import com.programmercarl.util.GenerateTreeNode;
import java.util.Stack;
/** * @ClassName HasPathSum * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 11:40 * @Version 1.0 * https://leetcode.cn/problems/path-sum/ * 112. 路径总和 **/
public class HasPathSum {
/** * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。 * 叶子节点 是指没有子节点的节点。 * <p> * ..不就是遍历每条路径和嘛 * * @param root * @param targetSum * @return */
public boolean hasPathSum(TreeNode root, int targetSum) {
//使用递归
if (root == null) {
return false;
}
return traversal(root, 0, targetSum);
}
public boolean traversal(TreeNode root, int sum, int targetSum) {
if (root == null) {
return sum == targetSum;
}
//只计算到叶子结点
sum += root.val;
//只计算右子树的结果
if (root.left == null && root.right != null) {
return traversal(root.right, sum, targetSum);
}
//只计算左子树的结果
if (root.left != null && root.right == null) {
return traversal(root.left, sum, targetSum);
}
return traversal(root.left, sum, targetSum) || traversal(root.right, sum, targetSum);
}
public static void main(String[] args) {
System.out.println(new HasPathSum().hasPathSum(GenerateTreeNode.generateTreeNode("[5,4,8,11,null,13,4,7,2,null,null,null,1]"), 22));
}
}
边栏推荐
- Successful entry into Baidu, 35K monthly salary, 2022 Android development interview answer
- 全网最全的低代码/无代码平台盘点:简道云、伙伴云、明道云、轻流、速融云、集简云、Treelab、钉钉·宜搭、腾讯云·微搭、智能云·爱速搭、百数云
- Complete interview questions for interviewers and senior Android engineers in front-line Internet enterprises
- okcc呼叫中心有什么作用
- ACM getting started Day1
- Android interview, Android audio and video development
- 测试的核心价值到底是什么?
- Do you know several assertion methods commonly used by JMeter?
- 如何安全快速地从 Centos迁移到openEuler
- Parler de threadlocal insecurerandom
猜你喜欢
【FAQ】华为帐号服务报错 907135701的常见原因总结和解决方法
Successful entry into Baidu, 35K monthly salary, 2022 Android development interview answer
Worthy of being a boss, byte Daniel spent eight months on another masterpiece
SecureRandom那些事|真伪随机数
Force buckle 1200 Minimum absolute difference
acm入门day1
UWB ultra wideband positioning technology, real-time centimeter level high-precision positioning application, ultra wideband transmission technology
After 95, Alibaba P7 published the payroll: it's really fragrant to make up this
What is the core value of testing?
Force buckle 729 My schedule I
随机推荐
IBM has laid off 40 + year-old employees in a large area. Mastering these ten search skills will improve your work efficiency ten times
Bitcoinwin (BCW) was invited to attend Hanoi traders fair 2022
Jvmrandom cannot set seeds | problem tracing | source code tracing
不愧是大佬,字节大牛耗时八个月又一力作
Float.floatToRawIntBits的返回值具体意思,将float转为byte数组
爬虫练习题(二)
众昂矿业:2022年全球萤石行业市场供给现状分析
【obs】libobs-winrt :CreateDispatcherQueueController
[C language] string function and Simulation Implementation strlen & strcpy & strcat & StrCmp
Realizing deep learning framework from zero -- LSTM from theory to practice [practice]
浅浅的谈一下ThreadLocalInsecureRandom
Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
Force buckle 1200 Minimum absolute difference
How to safely and quickly migrate from CentOS to openeuler
淺淺的談一下ThreadLocalInsecureRandom
【obs】QString的UTF-8中文转换到blog打印 UTF-8 char*
太牛了,看这篇足矣了
Reinforcement learning - learning notes 4 | actor critical
IBM大面积辞退40岁+的员工,掌握这十个搜索技巧让你的工作效率至上提高十倍
完爆面试官,一线互联网企业高级Android工程师面试题大全