Simple AC Java Solution DFS


  • 60
    S

    Each time find all the path start from current node
    Then move start node to the child and repeat.
    Time Complexity should be O(N^2) for the worst case and O(NlogN) for balanced binary Tree.

    public class Solution {
        public int pathSum(TreeNode root, int sum) {
            if(root == null)
                return 0;
            return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
        }
        
        public int findPath(TreeNode root, int sum){
            int res = 0;
            if(root == null)
                return res;
            if(sum == root.val)
                res++;
            res += findPath(root.left, sum - root.val);
            res += findPath(root.right, sum - root.val);
            return res;
        }
       
    }
    

    A better solution is suggested in 17ms O(n) java prefix sum by tankztc. It use a hash map to store all the prefix sum and each time check if the any subarray sum to the target, add with some comments:

        public int pathSum(TreeNode root, int sum) {
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, 1);  //Default sum = 0 has one count
            return backtrack(root, 0, sum, map); 
        }
        //BackTrack one pass
        public int backtrack(TreeNode root, int sum, int target, Map<Integer, Integer> map){
            if(root == null)
                return 0;
            sum += root.val;
            int res = map.getOrDefault(sum - target, 0);    //See if there is a subarray sum equals to target
            map.put(sum, map.getOrDefault(sum, 0)+1);
            //Extend to left and right child
            res += backtrack(root.left, sum, target, map) + backtrack(root.right, sum, target, map);
            map.put(sum, map.get(sum)-1);   //Remove the current node so it wont affect other path
            return res;
        }

  • 0
    W

    Hi, what's your time complexity for your solution?


  • 0
    Y

    same question, about the time complexity~


  • 0

    @yuhengw it is O(n^2)


  • 8
    I

    @elmirap Not exactly.

    If the tree is balanced, then each node is reached from its ancestors (+ itself) only, which are up to log n. Thus, the time complexity for a balanced tree is O (n * log n).

    However, in the worst-case scenario where the binary tree has the same structure as a linked list, the time complexity is indeed O (n ^ 2).


  • 0
    W

    @ivtoskov Agree with you, thanks!


  • 0
    S

    amazing solution


  • 0
    S

    superb solution


  • 0
    R

    Javascript solution for recursion version:

    var pathSum = function(root, sum) {
        if(!root) {
            return 0;
        }    
        return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    };
    
    var findPath = function(root, sum) {
        var res = 0;
        if(!root) return res;
        if(sum == root.val) res++;
        res += findPath(root.left, sum-root.val) + findPath(root.right, sum - root.val);
        return res;
    }
    

  • 2

    Treat each node as root, check subtree sum.

        public int pathSum(TreeNode root, int sum) {
          if(root == null) return 0;    
          int count = 0;
          count += pathSum(root.left, sum);
          count += pathSum(root.right, sum);
          count += sum(root, sum);
          return count;
        }
        
        int sum(TreeNode node, int sum){
          if(node == null) return 0;
          sum = sum - node.val;
          int count = 0;
          if(sum == 0) count++;
          count += sum(node.left, sum);
          count += sum(node.right, sum);
          return count;
        }

  • 0
    U

    amazing solution


  • 0
    K

    I have a question about id the path is from the grandchild of root to the end?


  • 0
    K

    and why the key is sum - target instead of target - sum


  • 0

    @star1993 said in Simple AC Java Solution DFS:

        map.put(sum, map.get(sum)-1);   //Remove the current node so it wont affect other path
        return res;
    

    The size remains O(n). To reduce to O(h), you should remove the sum.

    if(map.get(sum) == 0) map.remove(sum);
    return res;

  • 0
    N

    why need two function´╝î these two functions looks similar. could them be merge into one.

    '''

    public int pathSum(TreeNode root, int sum){
        int res = 0;
        if(root == null)
            return res;
        if(sum == root.val)
            res++;
        // without root
        res += pathSum(root.left, sum);
        res += pathSum(root.right, sum);
       // with root;
        res += pathSum(root.left, sum - root.val);
        res += pathSum(root.right, sum - root.val);
        return res;
    }  
    

    '''


  • 3
    Y

    @newdev Your solution is incorrect. It counts paths that are not connected.


  • 0
    N

    @star1993 Could you explain why it is O(NlogN) for balanced binary tree? Thank you.


  • 0
    N

    @ivtoskov What does the n mean? The number of nodes in tree?


  • 0
    C

    Why would BFS solution not work, i.e iterating through BFS and then finding the possibile paths from each node.

    class Solution {
    static int counter=0;
    public int pathSum(TreeNode root, int sum) {
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    if (root==null) return 0;
    q.add(root);
    while (!q.isEmpty()){
    TreeNode curr = q.remove();
    int x=sup(curr, sum);
    System.out.println(x);
    counter+=x;
    if (curr.left != null) q.add(curr.left);
    if (curr.right != null) q.add(curr.right);
    }
    return counter;
    }

    public int sup(TreeNode curr, int sum){
        int f=0;
        if (curr.val==sum) f++;
        if (curr.left== null && curr.right==null && curr.val!=sum) return 0;
        int left=0;
        int right=0;
        
        if (curr.left != null) {
            left = sup(curr.left, sum-curr.val);
        }
        if (curr.right != null) {
            right = sup(curr.right, sum-curr.val);
        }
        
        return f+left+right;
        
        
        
        
    }
    

    }


Log in to reply
 

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