Dictionary is not necessary, list is enough.

  • 1

    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>();
            foreach(int item in preSumList)
                int newSum = item+root.val;
                if(newSum == sum) paths++;
            paths = getPathCount(root.left, nextlist, sum, paths);
            paths = getPathCount(root.right, nextlist, sum, paths);
            return paths;

  • 0

    Thanks for sharing.

Log in to reply

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