Easy to understand Java solution with comment.


  • 8

    Any suggestion is greatly appreciated.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     
    /*
    for each parent node in the tree, we have 2 choices:
    1. include it in the path to reach sum.
    2. not include it in the path to reach sum. 
    
    for each child node in the tree, we have 2 choices:
    1. take what your parent left you.
    2. start from yourself to form the path.
    
    one little thing to be careful:
    every node in the tree can only try to be the start point once.
    
    for example, When we try to start with node 1, node 3, as a child, could choose to start by itself.
                 Later when we try to start with 2, node 3, still as a child, 
                 could choose to start by itself again, but we don't want to add the count to result again.
         1
          \
           2
            \
             3
             
    */ 
    public class Solution {
        int target;
        Set<TreeNode> visited;
        public int pathSum(TreeNode root, int sum) {
            target = sum;
            visited = new HashSet<TreeNode>();  // to store the nodes that have already tried to start path by themselves.
            return pathSumHelper(root, sum, false);
        }
        
        public int pathSumHelper(TreeNode root, int sum, boolean hasParent) {
            if(root == null) return 0;
            //the hasParent flag is used to handle the case when parent path sum is 0.
            //in this case we still want to explore the current node.
            if(sum == target && visited.contains(root) && !hasParent) return 0;
            if(sum == target && !hasParent) visited.add(root);
            int count = (root.val == sum)?1:0;
            count += pathSumHelper(root.left, sum - root.val, true);
            count += pathSumHelper(root.right, sum - root.val, true);
            count += pathSumHelper(root.left, target , false);
            count += pathSumHelper(root.right, target, false);
            return count;
        }
    }````

  • 5
    J

    I totally had the same idea with yours. But the my output was always greater than the expected answer. Now I understand that some child nodes have started several times. Thank you for your explanation. It really helped.


  • 2

    @jlchen You are welcome. Bu ke qi~~


  • 1

    @jlchen I met same problem like yours, now I know I need a visited hash set to avoid duplicates, learnt a lot here!


  • 0

    So what's the time complexity with this method?


  • 0

    @tankztc I think it is exponential, O(2^n)?


Log in to reply
 

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