【LeetCode】437. Path Sum III树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int>sums;
    int count=0;
    void travel(TreeNode * root ,int level ,int sum){
        if(root==NULL){return ;}
        sums[level] = sums[level-1]+root->val;
        for(int i=0;i<level;i++){
            if(sums[level]-sums[i]==sum)count++;
        }
        travel(root->left,level+1,sum);
        travel(root->right,level+1,sum);
    }
    int pathSum(TreeNode* root, int sum) {
        if(root == NULL){return 0;}
        sums.resize(maxDepth(root)+1,0);
        travel(root,1,sum);
        return count;
    }
    int maxDepth(TreeNode * root){
        if(root==NULL)return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
   
};