EZ to understand C# solution


  • 2
    C

    Time complexity: O(N^2)
    Space complexity: O(1)

    public class Solution {
    int result = 0;

    public int pathSum(TreeNode root, int sum) {
        if(root == null)
            return 0;
        includeRoot(root, sum);
        pathSum(root.left, sum);
        pathSum(root.right, sum);
        return result;
    }
    
     public void includeRoot(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        
        if (root.val == sum) {
            result++;
        }
        
        includeRoot(root.left, sum - root.val);
        includeRoot(root.right, sum - root.val);
    }
    

    }


  • 0
    S

    vary brilliant, thanks.
    xiexie:)


  • 0

    simplicity answer and easy to understand. How to reduce the N^2 time? I find it's hard to reduce to O(nlogn)


Log in to reply
 

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