[C++ DFS Concise]


  • 0
    H
    class Solution {
    public:
        void find (TreeNode *node, vector<int> &sums, int target, int &res) {
            sums.push_back(0);
            for (int i = 0; i < sums.size(); ++i) {
                sums[i] += node->val;
                if (sums[i] == target) ++res; 
            }
            if (node->left) find (node->left, sums, target, res);
            if (node->right) find (node->right, sums, target, res);
            
            sums.pop_back();
            for (int i = 0; i < sums.size(); ++i) sums[i] -= node->val;
        }
    
        int pathSum(TreeNode* root, int sum) {
            if (!root) return 0;
            
            int res = 0;
            vector<int> sums;
            find(root, sums, sum, res);
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.