C# version - O(n)


  • 0
    F
    public class Solution {
        int ans = 0, total = 0;
        Dictionary<int, int> dic = new Dictionary<int, int>();
        public void Traverse(TreeNode node, int s){
            if(node == null) return;
            if(dic.ContainsKey(node.val+s-total))
                ans += dic[node.val+s-total];
            if(dic.ContainsKey(s+node.val))
                dic[s+node.val]++;
            else dic.Add(s + node.val, 1);
            Traverse(node.left, s+node.val);
            if(node.left != null)
                dic[s+node.val+node.left.val]--;
            Traverse(node.right, s+node.val);
            if(node.right != null)
                dic[s+node.val+node.right.val]--;
        }
        public int PathSum(TreeNode root, int sum) {
            total = sum;
            dic.Add(0, 1);
            Traverse(root, 0);
            return ans;
        }
    }
    

Log in to reply
 

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