Count parent paths


  • 0
    T

    Straightforward - visit each node, test all paths leading to it, count the number of paths with the correct sum.

    public int pathSum(TreeNode root, int sum)
    {
        return recursive(new ArrayList<>(), root, sum);
    }
    
    int recursive(ArrayList<Integer> path, TreeNode node, int sum)
    {
        if(node==null) return 0;
        path.add(node.val);
    
        int count = 0;
        int s = 0;
        for(int i=path.size()-1; i>=0; i--)
        {
            s+=path.get(i);
            if(s==sum) count++;
        }
    
        count += recursive(path, node.left, sum);
        count += recursive(path, node.right, sum);
    
        path.remove(path.size()-1);
        return count;
    }

Log in to reply
 

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