原题链接:http://oj.leetcode.com/problems/path-sum/这道题是树操作的题目,判断是否从根到叶子的路径和跟给定sum相同的。还是用常规的递归方法来做,递归条件是看左子树或者右子树有没有满足条件的路径,也就是子树路径和等于当前sum减去当前节点的值。结束条件是如果当前节点是空的,则返回false,如果是叶子,那么如果剩余的sum等于当前叶子的值,则找到满足条件的路径,返回true。算法的复杂度是输的遍历,时间复杂度是O(n),空间复杂度是O(logn)。代码如下:public boolean hasPathSum(TreeNode root, int sum) {
if(root == null)
return false;
if(root.left == null && root.right==null && root.val==sum)
return true;
return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
}
树的题目在LeetCode中出现的频率很高,不过方法都很接近,掌握了就都差不多。这类求解树的路径的题目是一种常见题型,类似的还有Binary
Tree Maximum Path Sum,那道题更加复杂一些,路径可以起始和结束于任何结点(把二叉树看成无向图),有兴趣的朋友可以看看哈。
分享到:
相关推荐
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
四平方和定理 leetcode Leetcode practice Table of content Tree 92.reverse-linked-list-ii ...112.path-sum (路径总和) 116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点
多线程 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
3-leetcode-everyday 是时候拼一把了!!! DAY 1 1、two-sum 能同时获取元素和index的方法是使用enumerate() 思路:从第一个元素开始,遍历,求每个位置上的差值保存到dict中,如果在接下来的元素在dict中出现,...
//将每一种可能性都放入set中,并依次与sum对比public int pathSum(TreeNode root, int mySum){//1.递归出口/
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number ...LeetCode ...Sum ...Sum ...Sum ...Path Sum 73
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 做题笔记 按照知识点分类 链表 链表反转 分治: 回溯/递归 全排列问题,用visited变量; 组合问题,用start变量。 其它 动态规划 区间型 [从左上角到右下角] [子序列/子串:公共长度问题,都是DP,只有一个...
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-...
leetcode叫数 Leetcode_JS leetcode编程题,javascript版本 ##NO.35 Search Insert Position 这道题非常简单,数组是有序数组,只需要遍历一遍...Sum 这道题是关于二叉树的题,递归思路,也就是DFS的思路。 这里递归
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 — 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...
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/...
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...
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...
leetcode 树节点二叉树最大路径和 执行 : /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val ...
颜色分类leetcode 磁盘故障预测 只针对阿里巴巴AIOps岗位面试的编码测试 扫描当前目录下的所有CSV文件 import pandas as pd import glob , os , sys input_path = './' output_fiel = 'pandas_union_concat.csv' all...
第 338 章力码解决方案 问题编号 标题 困难 C Java Ruby 338 中等的 [✓](/src/338 计数位/solution.c) 104 简单的 [✓](/src/104 二叉树的最大深度/solution.c) ...Path Sum II/solution.java) 258 简单的 [✓](/
$ cd /path/to/leetcode/c/ # /path/to/leetcode/cpp/ $ mkdir build $ cd build $ cmake .. $ cd .. CMake将自动生成buildsystem文件并下载 。 注意:添加新的单元测试后,请务必重新加载CMake。 要构建,请使用--...
leetcode 18 java 小算法 python、Java或C中算法问题的一些实现 算法题主要来自leet code或者csc373 每日目标:关于 leetcode 的一个简单、中等或困难的问题以及 ...path_sum_ii.py merge_two_sorted_lists.py 5/24