Very clean C# solution - Beats 90% - Problem should be Medium on LeetCode, not easy


  • 1
    int result;
    public int PathSum(TreeNode root, int sum)
    {
        Dictionary<int, int> dict = new Dictionary<int, int>();
        dict.Add(0, 1);
    
        PathSumIII_helper(root, 0, sum, dict);
    
        return result;
    }
    private void PathSumIII_helper(TreeNode root, int curr_sum, int target_sum, Dictionary<int, int> dict)
    {
        if (root == null) return;
    
        curr_sum += root.val;
        int find = curr_sum - target_sum;
        if (dict.ContainsKey(find)) result += dict[find];
    
        AddOrIncrement(dict, curr_sum);
    
        PathSumIII_helper(root.left, curr_sum, target_sum, dict);
        PathSumIII_helper(root.right, curr_sum, target_sum, dict);
    
        RemoveOrDecrement(dict, curr_sum);
        curr_sum -= root.val;
    }
    
    private void AddOrIncrement(Dictionary<int, int> dict, int sum)
    {
        if (!dict.ContainsKey(sum))
            dict.Add(sum, 0);
        dict[sum]++;
    }
    private void RemoveOrDecrement(Dictionary<int, int> dict, int curr_sum)
    {
        if (dict[curr_sum] == 1) dict.Remove(curr_sum);
        else dict[curr_sum]--;
    }
    

Log in to reply
 

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