问题描述:
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22
,
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2
which sum is 22.
原问题链接:https://leetcode.com/problems/path-sum/
问题分析
这个问题的关键在于找到问题中的一个递归关系。因为如果要判断从根节点到某个叶节点是否存在这么一个节点值的和等于目标值,我们可以从一个节点当前的值和目标值判断。如果当前值已经是叶节点,而且和目标值相等,则返回true。否则同时递归的去看它的左右子节点和目标值的关系。
这里还有一个要注意的返回条件,就是当当前节点是null的时候,直接返回false。
详细的代码实现如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; if(root.val == sum && root.left == null && root.right == null) return true; return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); } }
相关推荐
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number ...LeetCode ...Sum ...Sum ...Sum ...Path Sum 73
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
LeetCode — Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need...
Path Sum Unique Paths Unique Paths II Longest Palindromic Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-...
Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary 单调栈 42. Trapping Rain Water 85. Maximal Rectangle Monotonic stack for 2d array 239. Sliding Window ...
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
$ cd /path/to/leetcode/c/ # /path/to/leetcode/cpp/ $ mkdir build $ cd build $ cmake .. $ cd .. CMake将自动生成buildsystem文件并下载 。 注意:添加新的单元测试后,请务必重新加载CMake。 要构建,请使用--...
371 | [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/) | [C++](./C++/sum-of-two-integers.cpp) [Python](./Python/sum-of-two-integers.py) | _O(1)_ | _O(1)_ | Easy | LintCode | ...
多线程 leetcode 前言 每天刷点leetcode,基于java语言...Path Sum II Copy List with Random Pointer Building H2O Fizz Buzz Multithreaded hard Merge k Sorted Lists Reverse Nodes in k-Group Trapping Rain Water
leetcode叫数 Leetcode_JS leetcode编程题,javascript版本 ##NO.35 Search Insert Position 这道题非常简单,数组是有序数组,只需要遍历一遍...Sum 这道题是关于二叉树的题,递归思路,也就是DFS的思路。 这里递归
leetcode 做题笔记 按照知识点分类 链表 链表反转 分治: 回溯/递归 全排列问题,用visited变量; 组合问题,用start变量。 其它 动态规划 区间型 [从左上角到右下角] [子序列/子串:公共长度问题,都是DP,只有一个...
113. Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree...
1、two-sum 能同时获取元素和index的方法是使用enumerate() 思路:从第一个元素开始,遍历,求每个位置上的差值保存到dict中,如果在接下来的元素在dict中出现,返回下标。。。真牛逼! 7、Reverse integer 字符串...
四平方和定理 leetcode Leetcode practice Table of content Tree 92.reverse-linked-list-ii ...112.path-sum (路径总和) 116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点
PATH 以从命令提示符访问。 快速开始: 使用 Github 登录: leetup user -g 使用cookie登录: leetup user -c leetup pick -l python 1 : leetup pick -l python 1 测试一个问题: leetup test two-sum.py -t "[1,2...
//将每一种可能性都放入set中,并依次与sum对比public int pathSum(TreeNode root, int mySum){//1.递归出口/
算法命令行界面设置样板来解决问题。 要使用CLI,请执行以下步骤cd bin/npm link用法al new [name] [arguments] 示例1... 示例2:带有参数al new path - sum node sum 输出var pathSum = function ( node , sum ) { } ;
leetcode 树节点二叉树最大路径和 执行 : /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val ...
leetcode 18 java 小算法 python、Java或C中算法问题的一些实现 算法题主要来自leet code或者csc373 每日目标:关于 leetcode 的一个简单、中等或困难的问题以及 ...path_sum_ii.py merge_two_sorted_lists.py 5/24
二、Python3程序64_Minimum_Path_Sum 最小路径和# 利用动态规划的方法# 要到达索引为[r,l]的网格# 一是从[r,l-1]的网格向右