3 lines of c++ solution


  • 79
    P
    bool hasPathSum(TreeNode *root, int sum) {
            if (root == NULL) return false;
            if (root->val == sum && root->left ==  NULL && root->right == NULL) return true;
            return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
        }

  • 0
    I

    I like the solution with the 'sum-root->val'. Instead of this I set the root->left->val+=root->val;
    But this is more elegant :)


  • 0
    V
    This post is deleted!

  • 4
    S
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL)  return false;
        if(root->right == root->left)  return sum == root->val;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val) ;
    }

  • 0
    C
    bool hasPathSum(TreeNode* root, int sum) {
            if (root == NULL) return false;
            if (root->val==sum && root->left==NULL && root->right==NULL) return true;
            return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
        }
    

    Yi Mao Yi Yang in Chinese!


  • 0
    F

    @CristianoJason The right pronounce is YI MO YI YANG.


  • 0
    I

    @pankit said in 3 lines of c++ solution:

    bool hasPathSum(TreeNode *root, int sum) {
            if (root == NULL) return false;
            if (root->val == sum && root->left ==  NULL && root->right == NULL) return true;
            return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
        }

  • 0
    S

    Came up with the same idea.


  • 0
    P
    This post is deleted!

  • 0
    N

    @frank40 Sorry, the real answer is YI MU YI YANG.


  • 0

    C# - same solution

    public bool HasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.val == sum && root.left == null && root.right == null)
        {
            return true;
        }
        
        return HasPathSum(root.left, sum - root.val) || HasPathSum(root.right, sum - root.val);
    }

  • 0
    S

    my straightforward but stupid solution, int DFS, i wonder when we should add another function like DFS_VISIT?

    class Solution {
    public:
        bool hasPathSum(TreeNode* root, int sum) {
            if(!root)
                return false;
            return pathSearch(root,sum,root->val);
        }
    private:
        bool pathSearch(TreeNode* root,int sum,int curSum)
        {
            if(!root->left && !root->right)
                return sum==curSum;
            if(root->left && root->right) return pathSearch(root->left,sum,curSum+root->left->val) || pathSearch(root->right,sum,curSum+root->right->val);
            else if(root->left) return pathSearch(root->left,sum,curSum+root->left->val);
            else return pathSearch(root->right,sum,curSum+root->right->val);
        }
    };

  • 0
    J

    Came up with the same idea.


  • 0
    J

    @pankit
    add one line : if (!root->left && !root->right && root->val != sum) return false;
    It's quicker when I submitted.


  • 0

    @jayzhu1215 The same idea! But no need to add one line, here is my solution:

    class Solution {
    public:
        bool hasPathSum(TreeNode* root, int sum)
        {
            if (!root) return false;
            if (!root->left && !root->right) return root->val == sum;
            return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
        }
    };
    

  • 0
    H

    Oh yeah, I like this awesome answer, clear and easy to understand :-D


  • 0
    V
    This post is deleted!

  • 0
    B

    @jdrogin
    this will return false if input is empty tree ( NULL) and sum =0.
    Ideally it should be true


Log in to reply
 

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