Dictionary is not necessary, list is enough.


  • 1

    C#
    No matter the current sum is equal target or not.
    You still have to carry it with value of current node to next level because 1-3 and 1-3-2-(-2) are two different paths.
    So here's my code. very easy to understand and straightforward.

        public int PathSum(TreeNode root, int sum) {
            List<int> preSumList=new List<int>();
            return getPathCount(root, preSumList, sum, 0);
        }
        
        public int getPathCount(TreeNode root, List<int> preSumList, int sum, int paths)
        {
            if(root == null) return paths;
            if(root.val == sum) paths++;
            List<int> nextlist = new List<int>();
            nextlist.Add(root.val);
            foreach(int item in preSumList)
            {
                int newSum = item+root.val;
                nextlist.Add(newSum);
                if(newSum == sum) paths++;
            }
            paths = getPathCount(root.left, nextlist, sum, paths);
            paths = getPathCount(root.right, nextlist, sum, paths);
            return paths;
        }

  • 0
    O

    Thanks for sharing.


Log in to reply
 

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