// 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 to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
// The tree 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
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
return pathCount(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
int pathCount(TreeNode node,int sum) {
if (node == null) {
return 0;
}
return (node.val == sum ? 1 : 0) + pathCount(node.left, sum - node.val) + pathCount(node.right, sum - node.val);
}
给定二叉树以及定值n，求连续子轨迹和为n的个数
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
