题目

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:

  1. root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
  3.       10
  4.      /  \
  5.     5   -3
  6.    / \    \
  7.   3   2   11
  8.  / \   \
  9. 3  -2   1
  11. Return 3. The paths that sum to 8 are:
  13. 1.  5 -> 3
  14. 2.  5 -> 2 -> 1
  15. 3. -3 -> 11

题意

在给定的树中找到一条从上到下的路径，使其和为给定值。路径的起点和终点可以是任意结点。

思路

双重递归。第一重递归确定根结点，限制需要查找的子树；第二重递归在该子树中找到从子树根结点出发和为sum的路径的个数。

代码实现

Java

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public int pathSum(TreeNode root, int sum) {
  18.         if (root == null) {
  19.             return 0;
  20.         }
  21.         return findPath(root, 0, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
  22.     }
  24.     private int findPath(TreeNode root, int curSum, int sum) {
  25.         if (root == null) {
  26.             return 0;
  27.         }
  28.         curSum += root.val;
  29.         return (curSum == sum ? 1 : 0) + findPath(root.left, curSum, sum) + findPath(root.right, curSum, sum);
  30.     }
  31. }