题目描述
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
思路
- 既然题目中说明不超过1000个结点,可以使用一个长度为1000的数组,用于保存所有结点的值。
2.可以抽象理解为vals[0]是vals[1]的父节点,vals[1]是vals[2]的父节点。 - 一个结点的路径总和为:rootNum = rootNum + leftNum + rightNum。
4.可以使用递归来处理求和,递归到某一结点时,自底向上的相加结点求和与target即可。
Java代码实现
class Solution {
private int num = 0;
public int pathSum(TreeNode root, int sum) {
int[] vals = new int[1000];
return pathSumDS(root,0,vals,sum);
}
private int pathSumDS(TreeNode root,int depth,int[] vals,int sum){
if(root == null)
return 0;
int rootVal = root.val;
int num = 0;
if(rootVal == sum){
num = 1;
}
for(int i=depth-1;i>=0;i--){
rootVal = rootVal + vals[i];
if(rootVal == sum){
num++;
}
}
vals[depth] = root.val;
int left = pathSumDS(root.left,depth+1,vals,sum);
int right = pathSumDS(root.right,depth+1,vals,sum);
return num+left+right;
}
}
Golang代码实现
func pathSum(root *TreeNode, sum int) int {
vals := make([]int,1000)
return pathSumDS(root,sum,0,vals)
}
func pathSumDS(root *TreeNode, sum int, depth int,vals []int) int {
if root == nil{
return 0
}
rootVal := root.Val
num := 0
if rootVal == sum{
num++
}
for i:=depth-1;i>=0;i--{
rootVal += vals[i]
if rootVal == sum{
num++
}
}
vals[depth] = root.Val
left := pathSumDS(root.Left,sum,depth+1,vals)
right := pathSumDS(root.Right,sum,depth+1,vals)
return num+left+right
}
有疑问加站长微信联系(非本文作者)