题目描述
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过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的数组,用于保存所有结点的值。
- 可以抽象理解为vals[0]是vals[1]的父节点,vals[1]是vals[2]的父节点。
- 一个结点的路径总和为:rootNum = rootNum + leftNum + rightNum。
- 可以使用递归来处理求和,递归到某一结点时,自底向上的相加结点求和与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 }