题目描述
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
437. 路径之和Ⅲ
解法1 递归
用了两个递归，第一个递归是算给定节点为根的树中有多少满足条件的路径；第二个递归是二叉树的每个节点都执行一次第一个递归。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//用于保存最后的路径总数
int res = 0;
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
//helper函数计算输入节点有多少条符合条件路径
helper(root, sum);
//左孩子
pathSum(root.left, sum);
//右孩子
pathSum(root.right, sum);
return res;
}
public void helper(TreeNode root, int sum) {
if (root == null) {
return;
}
//每遍历到一个节点，sum减去这个节点值
sum -= root.val;
if (sum == 0) {
res++;
/*
*这里一开始我写了条return，但是没过，发现在非叶
*子节点时sum到0就return而不往下遍历的话，会遗漏后续节点中相加为0的
*情况。例如 [1,-2,-3,1,3,-2,null,-1] 的二叉树，[1, -2]是，[1, -2, 1, -1]也是，
*如果这里有return，后面这条就递归不出来。
*/
}
helper(root.left, sum);
helper(root.right, sum);
}
}
解法2 递归加回溯
提交了第一种解法的代码后，去leetcode后台看了下数据，发现有人提交了3ms的结果（解法1 28ms），里面有更为惊艳的想法。
这篇讲得很清楚。
