当前位置:网站首页>[JZOF] 82 binary tree with a path of a certain value (1)
[JZOF] 82 binary tree with a path of a certain value (1)
2022-08-10 00:32:00 【sigh】
题目描述:
给定一个二叉树root和一个值 sum ,判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径.
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点.
2.叶子节点是指没有子节点的节点.
3.路径只能从父节点到子节点,不能从子节点到父节点.
4.总节点数目为n.
一、递归遍历:
import java.util.*;
public class Solution {
public boolean hasPathSum (TreeNode root, int sum) {
// write code here
if (root == null ) {
return false;
}
if (sum == root.val && root.left == null && root.right == null) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
二、层次遍历
import java.util.*;
/* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */
public class Solution {
/** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */
class Pair{
TreeNode node = null;
int curSum = 0;
// 内部类,Associate a partial path sum with the current node
public Pair(TreeNode node,int curSum){
this.node = node;
this.curSum = curSum;
}
}
public boolean hasPathSum (TreeNode root, int sum) {
// 根节点为空,返回false
if (root == null){
return false;
}
// Use a queue to store nodes during traversal
Queue<Pair> nodeQueue= new LinkedList<>();
Pair pair = new Pair(root,root.val);
nodeQueue.add(pair);
Pair curPair = null;
// 层次遍历,根,左,右
while(!nodeQueue.isEmpty()){
curPair = nodeQueue.poll();
// 左节点非空
if (curPair.node.left != null){
nodeQueue.add(new Pair(
curPair.node.left,
curPair.curSum+curPair.
node.left.val));
}
// 右节点非空
if (curPair.node.right != null){
nodeQueue.add(new Pair(
curPair.node.right,
curPair.curSum+curPair.
node.right.val));
}
// 判断是否为叶子节点,是则与sum进行比较
if (curPair.node.left==null&&curPair.node.right==null){
if (sum == curPair.curSum){
return true;
}
}
}
return false;
}
}
边栏推荐
- Interfering with BGP routing---community attributes
- 新增一地公布2022下半年软考报考时间
- 2022年最新《谷粒学院开发教程》:10 - 前台支付模块
- What is the stability of the quantitative trading interface system?
- Vmware中安装win7虚拟机以及相关简单知识
- OFDM 十六讲 7 - Inter-Symbol-Interference
- APS系统能消除造成生产和运输延迟的瓶颈
- 直播预告 | ICML 2022 11位一作学者在线分享神经网络,图学习等前沿研究
- tiup cluster start
- Basic operations of xlrd and xlsxwriter
猜你喜欢
HUAWEI CLOUD escorts the whole process of "Wandering Ark" for the first time, creating a popular brand
【Burning】It's time to show your true strength!Understand the technical highlights of the 2022 Huawei Developer Competition in one article
HBuilder X 不能运行到内置终端
shader学习笔记(五)
离散选择模型之Gumbel分布
安踏携手华为运动健康共同验证冠军跑鞋 创新引领中国体育
【技术分享】SLA(服务等级协议)原理与配置
用PLSQL导出Oracle一个表
ArrayList 和 LinkedList 区别
数字与中文大写数字互转(5千万亿亿亿亿以上的数字也支持转换)
随机推荐
33. Fabric通道、组织、节点、权限间关系
tiup cluster upgrade
金仓数据库 KingbaseGIS 使用手册(6.6. 几何对象校验函数、6.7. 空间参考系函数)
SRv6性能测量
1018.值周
shell数组
【Burning】It's time to show your true strength!Understand the technical highlights of the 2022 Huawei Developer Competition in one article
杂谈——程序员的悲哀
全球不用交税的国家,为什么不交
测试2年,当时身边一起入行的朋友已经月薪20k了,自己还没过万,到底差在了哪里?
Interfering with BGP routing---community attributes
杭电多校-Counting Stickmen-(思维+组合数+容斥)
金仓数据库 KingbaseGIS 使用手册(6.3. 几何对象创建函数)
直播预告 | ICML 2022 11位一作学者在线分享神经网络,图学习等前沿研究
HUAWEI CLOUD escorts the whole process of "Wandering Ark" for the first time, creating a popular brand
setter与getter访问器属性——数据驱动显示
leetcode 20. Valid Parentheses 有效的括号(中等)
2022-8-9 第六组 输入输出流
Gartner全球集成系统市场数据追踪,超融合市场增速第一
2022-08-09 mysql/stonedb-子查询性能提升-概论