当前位置:网站首页>Leetcode skimming: binary tree 16 (path sum)
Leetcode skimming: binary tree 16 (path sum)
2022-07-05 20:03:00 【Taotao can't learn English】
112. The sum of the paths
Given a binary tree and a target and , Determine whether there is a path from root node to leaf node in the tree , The sum of the values of all nodes in this path is equal to the target and .
explain : A leaf node is a node that has no children .
Example :
Given the following binary tree , And goals and sum = 22,
return true, Because there are goals and for 22 The path from the root node to the leaf node 5->4->11->2.
Recursive traversal , If there are only left trees , Then only the left subtree is calculated , If only the right subtree , Then only the right subtree is calculated , If you encounter an empty node, start comparing , Put the recursive result or operation that will do .
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. The sum of the paths **/
public class HasPathSum {
/** * Give you the root node of the binary tree root And an integer representing the sum of goals targetSum . Determine if there is Root node to leaf node The path of , The sum of the values of all nodes in this path is equal to the target and targetSum . If there is , return true ; otherwise , return false . * Leaf node A node without children . * <p> * .. It's just to traverse every path and * * @param root * @param targetSum * @return */
public boolean hasPathSum(TreeNode root, int targetSum) {
// Using recursion
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;
}
// Calculate only to leaf nodes
sum += root.val;
// Only the result of right subtree is calculated
if (root.left == null && root.right != null) {
return traversal(root.right, sum, targetSum);
}
// Only calculate the result of the left subtree
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));
}
}
边栏推荐
- leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
- 怎么挑选好的外盘平台,安全正规的?
- 微信小程序正则表达式提取链接
- 【c语言】归并排序
- 城链科技数字化创新战略峰会圆满召开
- leetcode刷题:二叉树15(找树左下角的值)
- sun.misc.BASE64Encoder报错解决方法[通俗易懂]
- After 95, Alibaba P7 published the payroll: it's really fragrant to make up this
- Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
- How about testing outsourcing companies?
猜你喜欢
- Oui. Net Distributed Transaction and Landing Solution
leetcode刷题:二叉树12(二叉树的所有路径)
Interviewer: what is the internal implementation of set data types in redis?
图嵌入Graph embedding学习笔记
Parler de threadlocal insecurerandom
What is the core value of testing?
[OBS] qstring's UTF-8 Chinese conversion to blog printing UTF-8 char*
【无标题】
Based on vs2017 and cmake GUI configuration, zxing and opencv are used in win10 x64 environment, and simple detection of data matrix code is realized
ACM getting started Day1
随机推荐
Where is the operation of new bonds? Is it safer and more reliable to open an account
B站UP搭建世界首个纯红石神经网络、基于深度学习动作识别的色情检测、陈天奇《机器学编译MLC》课程进展、AI前沿论文 | ShowMeAI资讯日报 #07.05
1: Citation;
C - sequential structure
Recommended collection, my Tencent Android interview experience sharing
C language OJ gets PE, OJ of ACM introduction~
CADD课程学习(7)-- 模拟靶点和小分子相互作用 (半柔性对接 AutoDock)
Bzoj 3747 poi2015 kinoman segment tree
秋招字节面试官问你还有什么问题?其实你已经踩雷了
JVMRandom不可设置种子|问题追溯|源码追溯
ACM getting started Day1
浅浅的谈一下ThreadLocalInsecureRandom
Wechat applet regular expression extraction link
618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
openh264解码数据流向分析
C application interface development foundation - form control (5) - grouping control
SecureRandom那些事|真伪随机数
Leetcode skimming: binary tree 10 (number of nodes of a complete binary tree)
Jvmrandom cannot set seeds | problem tracing | source code tracing
Cocos2d-x项目总结中的一些遇到的问题