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);
    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.