437. 路径总和 III
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过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 -> 1
思路一：双重递归
写法一：
1 class Solution { 2 public boolean flag = false; 3 public int cnt = 0, cntSum = 0; 4 public int pathSum(TreeNode root, int sum) { 5 preTraversal(root, sum); 6 return cntSum; 7 } 8 9 // 回溯每个结点判断从根节点开始往下是否存在等于sum的路径 10 public void traceBack(TreeNode root, int nowSum, int sum){ 11 if(root != null){ 12 nowSum += root.val; 13 if(sum == nowSum){ 14 cnt++; 15 } 16 traceBack(root.left, nowSum, sum); 17 traceBack(root.right, nowSum, sum); 18 } 19 } 20 21 // 遍历树的所有结点，对每个结点判断从根节点开始往下是否存在等于sum的路径 22 // 前序递归遍历树节点 23 public void preTraversal(TreeNode root, int sum){ 24 if(root != null){ 25 cnt = 0; 26 traceBack(root, 0, sum); 27 cntSum += cnt; 28 preTraversal(root.left, sum); 29 preTraversal(root.right, sum); 30 } 31 } 32 }
力扣测试时间为31ms, 空间为39.2MB
另一中稍微简洁一点的写法是：
1 class Solution { 2 public int pathSum(TreeNode root, int sum) { 3 if(root == null){ 4 return 0; 5 } 6 // 求出以root为根和为sum的的路径条数 7 int result = traceBack(root, sum); 8 // 递归以root.left为根和为sum的的路径条数 9 int left = pathSum(root.left, sum); 10 // 递归以root.right为根和为sum的的路径条数 11 int right = pathSum(root.right, sum); 12 return result + left + right; 13 } 14 15 // 回溯每个结点判断从根节点开始往下是否存在等于sum的路径 16 public int traceBack(TreeNode root, int sum){ 17 if(root == null){ 18 return 0; // 到达根节点直接返回0 19 } 20 sum -= root.val; 21 int result = sum == 0 ? 1 : 0; 22 // 加上包含左右根节点的路径 23 return result + traceBack(root.left, sum) + traceBack(root.right, sum); 24 } 25 }
力扣测试时间为31ms, 空间为39.7MB（可以看到两种写法的时间都差不多，毕竟都是进行先序遍历，对每个结点再已它为根进行一次前序遍历）
复杂度分析：
时间复杂度：先进行先序遍历，对每个结点再已它为根进行一次前序遍历，所以时间复杂度为O(n^2)
空间复杂度：在最坏情况下，即树变成单链表时，栈的最大为n^2, 所以空间复杂度为O(n^2),
思路二：（不太懂，以后回来看）
可以理解为以当前结点为最终叶子结点向上追溯，路径上的任一结点为根节点到当前结点的路径和为sum的路径个数。 然后以同样的方法以自己的孩子结点为最终叶子结点计算。
1 class Solution { 2 public int pathSum(TreeNode root, int sum) { 3 // 把以当前结点为终止结点的路径和加入到数组中 4 return helper(root, sum, new int[1000], 0); // 0表示刚开始的终结结点为0 5 } 6 public int helper(TreeNode root, int sum, int[] array, int p){ 7 if(root == null){ 8 return 0; 9 } 10 // 判断以当前根节点为终止结点是否存在满足要求的路径 11 // 当前结点既是根节点也是终止结点 12 int temp = root.val; 13 int cnt = (temp == sum ? 1 : 0); 14 // 把每个结点都作为开始结点，判断结点到当前结点是否符合要求 15 for(int i = p - 1; i >= 0; i--){ 16 temp += array[i]; 17 cnt += (temp == sum ? 1 : 0); 18 } 19 array[p] = root.val; 20 // 求出以左右子节点为终止结点，求出符合要求的路径数量 21 int cnt1 = helper(root.left, sum, array, p + 1); 22 int cnt2 = helper(root.right, sum, array, p + 1); 23 return cnt1 + cnt2 + cnt; 24 } 25 26 }
力扣测试时间为4ms, 空间为39.6MB
复杂度分析：
时间复杂度：虽然变成了单递归，但是复杂度仍然是O(n^2)
空间复杂度：栈的深度最大可大n, 所以空间复杂度为O(n)