- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/path-sum-iii/#/descriptionopen in new window
Youare given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
Thepath does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
Thetree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
找到二叉树中从某个顶点向下找的路径中,有多少条等于sum.
使用DFS解决。dfs函数有两个参数,一个是当前的节点,另一个是要得到的值。当节点的值等于要得到的值的时候说明是一个可行的解。再求左右的可行的解的个数,求和之后是所有的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int pathSum(TreeNode root, int sum) {
if(root == null){
return 0;
}
return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
public int dfs(TreeNode root, int sum){
int res = 0;
if(root == null){
return res;
}
if(root.val == sum){
res++;
}
res += dfs(root.left, sum - root.val);
res += dfs(root.right, sum - root.val);
return res;
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
python代码如下:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
if not root: return 0
return self.dfs(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
def dfs(self, root, sum):
res = 0
if not root: return res
sum -= root.val
if sum == 0:
res += 1
res += self.dfs(root.left, sum)
res += self.dfs(root.right, sum)
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
使用BFS找到每个顶点作为起点的情况下,用dfs计算等于sum的路径个数。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
res = [0]
que = collections.deque()
que.append(root)
while que:
node = que.popleft()
if not node:
continue
self.dfs(node, res, 0, sum)
que.append(node.left)
que.append(node.right)
return res[0]
def dfs(self, root, res, path, target):
if not root: return
path += root.val
if path == target:
res[0] += 1
self.dfs(root.left, res, path, target)
self.dfs(root.right, res, path, target)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
题目地址:https://leetcode.com/problems/my-calendar-iii/description/ 题目描述: Implement a MyCalendarThree
题目地址:https://leetcode.com/problems/house-robber-iii/description/ 题目描述 Thethief has found himself a
题目地址:https://leetcode.com/problems/combination-sum-iii/description/ 题目描述: Find all possible combin
题目地址:https://leetcode.com/problems/path-sum-iii/#/descriptionopen in new window 题目描述 Youare given
题目地址:https://leetcode.com/problems/max-consecutive-ones-iii/ 题目描述 Given an array A of 0s and 1s, w
题目地址:https://leetcode-cn.com/problems/shortest-word-distance-iii/ 题目描述 Given a list of words and t
题目地址:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/ 题目描述 Sayyou ha
1.题目 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。 除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有
1.题目 给定一个字符串 s ,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例 1: 输入:s = “Let’s take LeetCode contest” 输出:“s
1.题目 给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的路径的数目。 路径不需要从根节点开始,也不需要在叶子节点结束,但是路径
有两个正在运行的Docker容器。一个包含Web应用程序的容器,另一个包含链接的postgres数据库。 Pgadmin III工具应安装在哪里? 最佳答案 pgAdmin can be deploy
一、题目 给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数 组中连续 1 的最大个数 。 二、示例 输入:nums = [1,1,1,0,0,0,1,1,1,1
我有以下 java 代码框架 - try { Question q = null; //List of questions. I have put 3 in t
我有一个数据集,我想用它来比较物种和栖息地对家园大小的影响 - 同时使用 III 型错误和物种和栖息地内的成对比较。 这是数据的一个子集: species<- c("a","b","c","c","b
我的应用需要使用罗盘显示设备的当前方位。我正在使用的代码(下方)在我的 Galaxy Nexus 和 Galaxy One 上运行得非常好,但指南针在三星 Galaxy S III 上却疯狂地旋转。我
我的 pgAdmin 突然显示两个连接到同一个服务器(本地主机)。 我不记得今天打开软件前最后一次做了什么具体操作。 两台服务器包含相同的数据库和登录角色。 问: 为什么会这样? 只删除/删除其中一个
我在 pgAdmin 上查询时偶然发现了这种奇怪的行为。 我已连接到运行 PostgreSQL 9.1.9 的服务器。 我有一个名为 messages 的表,其定义如下: ghareh@godot:~
我最近安装了 pgAdmin III 1.18.1 并注意到一件奇怪的事情: 长json查询结果缩短为256个符号,然后添加'(...)'。 有人可以帮我禁用这个缩短吗? 最佳答案 感谢用户Erwin
leetcode 问题是: Find all possible combinations of k numbers that add up to a number n, given that only
John Carmack 在 Quake III 源代码中有一个特殊函数,它计算 float 的平方根倒数,比常规 (float)(1.0/sqrt(x)) 快 4 倍,包括奇怪的 0x5f3759d
我是一名优秀的程序员,十分优秀!