Simple backtrace solution with c language


  • 0
    T
    int find_val_sum(int *path, int idx, int sum)
    {
        int i = 0;
        int s = 0;
        int p = 0;
    
        for (i=idx; i>=0; i--) {
            s += path[i];
            if (s == sum) {
                p++;
            }
        }
    
        return p;
    }
    
    void path_sum(struct TreeNode *root, int *path, int idx, int sum, int *nr_path)
    {
        if (root == NULL)
            return;
        path[idx] = root->val;
        *nr_path += find_val_sum(path, idx, sum);
        path_sum(root->left, path, idx+1, sum, nr_path);
        path_sum(root->right, path, idx+1, sum, nr_path);
    }
    
    int pathSum(struct TreeNode* root, int sum) {
        int *path = malloc(sizeof(int) * 1000);
        int idx = 0;
        int nr_path = 0;
        path_sum(root, path, idx, sum, &nr_path);
        free(path);
        return nr_path;
    }
    

Log in to reply
 

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