C++ straight forward solution


  • 5
    J
    class Solution {
    public:
        int pathSum(TreeNode* root, int sum) {
            int res = 0;
            pathSumHelper(root, sum, res, false);
            return res;
        }
        void pathSumHelper(TreeNode* root, int sum, int &res, bool parent_used) {
            if (!root)
                return;
            if (sum - root->val == 0)
                res++;
            pathSumHelper(root->left, sum - root->val, res, true);
            pathSumHelper(root->right, sum - root->val, res, true);
            if (parent_used == false) { //if parent is part of the sum, then we cannot start a new path which jump over this node
                pathSumHelper(root->left, sum, res, false);
                pathSumHelper(root->right, sum, res, false);
            }
        }
    };
    

Log in to reply
 

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