Simple Java DFS


  • 67
    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);
        }
    }
    

  • 4
    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?


  • 0

    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.


  • 2
    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.


  • 4
    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.


  • 0
    B

    @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!

Log in to reply
 

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