Simple Java DFS


  • 136
    J

    Typical recursive DFS.
    Space: O(n) due to recursion.
    Time: O(n^2) in worst case (no branching); O(nlogn) in best case (balanced tree).

    public class Solution {
        public int pathSum(TreeNode root, int sum) {
            if (root == null) return 0;
            return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
        }
        
        private int pathSumFrom(TreeNode node, int sum) {
            if (node == null) return 0;
            return (node.val == sum ? 1 : 0) 
                + pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
        }
    }
    

  • 6
    F

    I think this solution is much elegant than the most up-voted one which is the same recursive solution, why there is nobody comment on it?


  • 2

    intuitive solution and easy understand


  • 0
    A

    Yours is the best solution here, precisely because it is very easy to understand! I wish it had more upvotes.


  • 4
    D

    At first I just cannot figure out why pathSum needs to be called again.
    Then I realized that it because each node could be exactly the sum itself.
    If we only call pathSumFrom; the cases which node value == sum would be bypassed.

    Simple and fast!! Thank you.


  • 7
    Y

    because the time complexity is not as good as using HashMap.


  • 0
    M

    If we change the condition in pathSumFrom method from (node.val == sum) to (sum == 0), then it is not returning the correct answer. Why is that so ?


  • 0
    D

    @manav.bhanot.86 because you should use if(node.val==0) instead


  • 0
    M

    @damon03 I do not think that will also work. node.val is something which is fixed and is not altered and sum is the variable that is being decreased every time.


  • 1

    @jiangsichu I wrote the following solution in C++, which is quite similar to your solution:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        int count=0;
    public:
        int pathSumUtil(TreeNode* root, int sum) {
            if(root==NULL)
                return 0;
            if(root->val==sum) {
                count++;
            }
            pathSumUtil(root->left, sum-(root->val));
            pathSumUtil(root->right, sum-(root->val));
            
            return count;
        }
        int pathSum(TreeNode* root, int sum) {
            if(root==NULL)
                return 0;
                
            pathSum(root->left, sum);
            pathSumUtil(root, sum);
            pathSum(root->right, sum);
            
            return count;
        }
    };
    

    However, I had one question - How did you come up with the time complexities, especially the best case? I understand it is O(n^2) in the worst case since we visit all the nodes starting with the current one... But how is it O(nlogn) in the best case. Specifically, what exactly do you mean when you say:

    O(nlogn) in best case (balanced tree).

    Thank you!


  • 0
    X

    My way to do it, a little bit different.

    public int pathSum(TreeNode root, int sum) {
        if (root == null)
          return 0;
        return dfs(root, sum, 0) + pathSum(root.left, sum) + pathSum(root.right, sum);
      }
    
      private int dfs(TreeNode root, int sum, int cur) {
        if (root == null)
          return 0;
        cur += root.val;
        return (cur == sum ? 1 : 0) + dfs(root.left, sum, cur) + dfs(root.right, sum, cur);
      }
    

  • 0
    L
    This post is deleted!

  • 0

    Fantastic!!!!!!!!!!!!!!!


  • 0
    L

    Hi @jiangsichu and everyone, I get wrong answer from the following code. Can you help point out what I'm missing? Thank you!

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

  • 1
    L

    @linxingquan said in Simple Java DFS:

    Hi @jiangsichu and everyone, I get wrong answer from the following code. Can you help point out what I'm missing? Thank you!

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

    Ah, I see the problem here. pathSum(root.left, sum) and pathSum(root.left, sum-root.val) can possibly count the result twice. Same to the right subtree.


  • 1
    C

    @BatCoder Let me try to explain the time complexity of O(nlogn) when tree is balanced. For each node, "pathSumFrom" method cost O(n) time, n is number of nodes below it. The solution calls "pathSumFrom" for each node. In each layer, the total time is O(n). There are total of logn layers. So total is O(nlogn). I.e. layer 1 + layer 2 + ... + layer logn = n + (n/2)*2 + (n/4)*4 + ... = nlogn


  • 0

    @ccyjoshua Thank you. This is helpful. :)


  • 0
    Y

    @ccyjoshua said in Simple Java DFS:

    "pathSumFrom" method cost O(n) time

    @ccyjoshua said in Simple Java DFS:

    The solution calls "pathSumFrom" for each node

    So it is n^2


  • 0
    G

    @manav.bhanot.86 Is it because when recurse to the leaf node when sum == 0, it returns 0 directly without adding anything


  • 0
    A

    @yukas66 He has already mentioned that the n in O(n) is the number of nodes below it. So here a better way to understand it is that suppose we on have one side tree, it is like a linked list, then at the first node, it will take n to get the result. For the second node, it will cost n - 1, for the 3rd one it will take n - 2 and so on. So it is an Arithmetic progression which is (1 + n) * n / 2 which is O(n^2).


Log in to reply
 

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