437. Path Sum III

https://leetcode.com/problems/path-sum-iii/description/
Solution 0.  Recursion:
If the parent node is not used, the current node is the start of a new path. We should also start a new path from its leaves.
No matter the parent node is used or not, the current path should be continued through its leaves.
    void preOrder(TreeNode* node, int s, int& res, bool isParentUsed) {
        if(!node) return;
        if(s - node->val == 0) res++;
        // the current path continues through the leaves of the current node
        preOrder(node->left, s - node->val, res, true);
        preOrder(node->right, s - node->val, res, true);
        if(!isParentUsed) {
            // start a new path from the leaves of current node if parent is not used.
            // here s equal to the target "sum"
            preOrder(node->left, s, res, false);
            preOrder(node->right, s, res, false);
        }
    }
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        int res = 0;
        preOrder(root, sum, res, false);
        return res;
    }
Solution 1. Do recursion sum from root to a node, increase path numbers if sum is equal to target. Then do a recursion for subtrees.
    int sumFromNode(TreeNode* node, int sum, int s) {
        if(!node) return 0;
        s += node->val;
        return (s == sum)
            + sumFromNode(node->left, sum, s)
            + sumFromNode(node->right, sum, s);
    }
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        return sumFromNode(root, sum, 0)
            + pathSum(root->left, sum)
            + pathSum(root->right, sum);
    }
or,


    void sumFromNode(TreeNode* node, const int sum, int s, int& np) {
        if(!node) return;
        s += node->val;
        if(s == sum) np++;
        sumFromNode(node->left, sum, s, np);
        sumFromNode(node->right, sum, s, np);
    }
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        int np = 0;
        sumFromNode(root, sum, 0, np);
        return np + pathSum(root->left, sum) + pathSum(root->right, sum);
    }
Solution 2.0 A stupid solution. Use only one recursion, by saving the sums to an array.
    void preOrder(TreeNode* node, int sum, vector<int>& s, int& np) {
        if(!node) return;
        s.push_back(0);
        for(int i=0; i<s.size(); i++) {
            s[i] += node->val;
            if(s[i] == sum) np++;
        }
        preOrder(node->left, sum, s, np);
        preOrder(node->right, sum, s, np);
        s.pop_back();
        for(int i=0; i<s.size(); i++) {
            s[i] -= node->val;
        }
    }
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        vector<int> s;
        int np = 0;
        preOrder(root, sum, s, np);
        return np;
    }
Solution 2.1
    void preOrder(TreeNode* node, int sum, vector<int> s, int& np) {
        if(!node) return;
        s.push_back(0);
        for(vector<int>::iterator it=s.begin(); it<s.end(); it++) {
            *it += node->val;
            if(*it == sum) np++;
        }
        preOrder(node->left, sum, s, np);
        preOrder(node->right, sum, s, np);
    }
    int pathSum(TreeNode* root, int sum) {
        int np = 0;
        vector<int> s;
        preOrder(root, sum, s, np);
        return np;
    }