当前位置:网站首页>【JZOF】82二叉树中和为某一值的路径(一)
【JZOF】82二叉树中和为某一值的路径(一)
2022-08-09 22:11:00 【叹了口丶气】
题目描述:
给定一个二叉树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;
// 内部类,将部分路径和与当前节点相关联
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;
}
// 使用队列在遍历过程中存储节点
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;
}
}
边栏推荐
猜你喜欢
随机推荐
tiup cluster upgrade
&&、||、&、|
探索TiDB Lightning源码来解决发现的bug
2020年度SaaS TOP100企业名单
JS--hashchange事件--使用/教程
【Apifox】为什么如此受青睐,此篇文章和大家分享
leetcode 20. Valid Parentheses 有效的括号(中等)
力扣:518. 零钱兑换 II
HUAWEI CLOUD escorts the whole process of "Wandering Ark" for the first time, creating a popular brand
“我“是一名测试/开发程序员,小孙的内心独白......
tiup cluster scale-out
学习编程的第十二天
LeetCode_2632_字符串压缩
对象深复制,面试题
深度学习100例 —— 循环神经网络(RNN)实现股票预测
iNFTnews | 迪士尼如何布局Web3
力扣:279.完全平方数
【Leetcode】2104. Sum of Subarray Ranges
(转)FreeType字体位图属性
Leetcode 701. 二叉搜索树中的插入操作