Tree Path Sum III

https://leetcode.com/problemset/algorithms/
题意是在一颗树中统计 多个连续节点的和等于某一个值sum的组合数(相邻节点必须是父子关系)

我的思路是 递归返回一个数组记录一个节点所对应的各条路径对应的和
例如树[1,2,3,4,5,6,7]
1
2 3
4 5 6 7
以节点2为例以它为起点的路径所有节点的和分别为2、2+4、2+5三种选择，对应数组[2,6,7]，同理以节点3为起点对应的数组是[3,9,10]。如果以节点1为起点则它的“路径和”分别为1，1+2,1+6,1+7
,1+3,1+9,1+10 [1,3,7,8,4,10,11]。然后可以通过统计每个节点对应的路径和中与sum相等的个数。

class Solution {
public:
    int result;
    int pathSum(TreeNode* root, int sum) {
        recusion(root, sum);
        return result;
    }
    
    vector<int> recusion(TreeNode* root, int sum){
         vector<int> vecAll;//供父节点选择
         if(root == NULL){
            return vecAll;
         }
        
         if(root->val == sum){
            result++;   
         }
        
         if((root->right == NULL)&&(root->left == NULL)){
            vecAll.push_back(root->val);
            return vecAll;
         }
        
         vector<int> vecLeft = recusion(root->left, sum);
         vector<int> vecRight = recusion(root->right, sum);
       
         vecLeft.insert(vecLeft.end(), vecRight.begin(), vecRight.end()); 
         vecAll = vecLeft;
        
        for(vector<int>::iterator it = vecAll.begin(); it!=vecAll.end(); it++)
      {
            int i = *it;
            int jude = root->val+i;
            if(jude == sum){
                result++;
            }
            *it = *it+root->val;
        }
        vecAll.push_back(root->val);
        return vecAll;
    }
};

下面是一个更巧妙的算法。是从头节点为起点计算各种符合条件的“路径和”。sumUp方法通过递归计算出以对应节点root为起点所对应的所有的符合条件的路径的数目，然后通过pathSum递归计算出以root节点的子节点为起点符合条件的路径数目，后将统计出的相加便是最后的结果。

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        return sumUp(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
    }
private:
    int sumUp(TreeNode* root, int pre, int& sum){
        if(!root) return 0;
        int current = pre + root->val;
        return (current == sum) + sumUp(root->left, current, sum) + sumUp(root->right, current, sum);
    }
};