题：https://leetcode.com/problems/path-sum-iii/description/

#题目 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

思路

题目分析

二叉树中，选取一个节点和它子节点，若从该节点到其子节点所有节点之和为 sum。那么视为 一条成功的路径。 给定一个 二叉树 和 sum，统计出 成功路径 的个数。

解题思路

第一版

分两步： 第一步：对于 一个作为起点的节点，它有所有子节点组成的成功路径有多少。 第二步：计算 每个节点 为起点的 成功路径，然后求和。

给定一个根节点 计算 它到每个子节点时所经过所有节点上 val的和。 代码为 dfs 。

第一步

def dfs(root,remainder): if root == None: return 0 res = 0 if root.val == remainder: res += 1 return res + dfs(root.left,remainder - root.val) + dfs(root.right,remainder - root.val)

第二步

def pathSum(self, root, sum): """ :type root: TreeNode :type sum: int :rtype: int """ if root == None: return 0 return dfs(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)

code

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None def dfs(root,remainder): if root == None: return 0 res = 0 if remainder == root.val: res += 1 return res+dfs(root.left,remainder - root.val) + dfs(root.right,remainder - root.val) class Solution: def pathSum(self, root, sum): """ :type root: TreeNode :type sum: int :rtype: int """ if root == None: return 0 return dfs(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)

第二版

问题划分，求一个子树中，一段相连结点的和为 sum。

递归函数： int pathSumStartWithRoot（root，sum） 返回 从root结点出发，有连续路径为sum的个数。 对于 结点 troot的 递归方程： pathSumStartWithRoot（troot，sum） == [0/1]（若该点的val 等于 sum，即 以该点为终点）+ pathSumStartWithRoot（troot.left，sum - troot.val）（以troot为 路径的一段，往左延伸）+ pathSumStartWithRoot（troot.right，sum - troot.val）（以troot为 路径的一段，往右延伸）。 递归边界：若当前 root==null，那么该结点的pathSumStartWithRoot应该为0。

递归函数：int pathSum(root，sum) 返回 root 及其 子树 所有结点的 连续路径为sum的个数。

递归方程：pathSum（root，sum） = pathSumStartWithRoot（root，sum）（以root结点为开始的 路径）+ pathSum(root.left，sum) （root 左子树的所有 连续路径为sum的个数）+pathSum(root.right，sum) （root 右子树的所有 连续路径为sum的个数）

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int pathSum(TreeNode root, int sum) { if(root == null) return 0; int res = pathSumStartWithRoot(root,sum) + pathSum(root.left,sum)+pathSum(root.right,sum); return res; } public int pathSumStartWithRoot(TreeNode root,int sum){ if(root == null) return 0; int res = 0; if(root.val == sum) res++; res += pathSumStartWithRoot(root.left,sum -root.val) + pathSumStartWithRoot(root.right,sum-root.val); return res; } }