My solution (trace the whole tree)


  • 0
    A
    class Solution {
    public:
    bool hasPathSum(TreeNode *root, int sum) {
        bool ans = false;
        if(root)        
            findPath(root, ans, sum, root -> val);
        return ans;
    }
    void findPath(TreeNode *root, bool &ans, int sum, int val){
        if(ans)
            return;
            
        if(!root -> right && !root -> left){
            if(sum == val)
                ans = true;
            return;
        }
        
        if(root -> left)
            findPath(root -> left, ans, sum, val + root -> left -> val);
        if(root -> right)
            findPath(root -> right, ans, sum, val + root -> right -> val);
    }
    };

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 1
    L

    Accepted : Preorder tree Traversal (without driver function)

     bool hasPathSum(TreeNode *root, int sum) {
       //If root is null there is no question of existence of a path ,so return false   
             if(!root)      
                return false;
             
       //For a leaf node check if root->value is equal to sum
             if(root->right==NULL && root->left==NULL)  
               return (sum==root->val)?true:false;
    
        //If no right tree for root, find sum in left tree by deducting root->val from sum
             if(!root->right)               
               return hasPathSum(root->left,sum-root->val);
             
         //Doing same as above if no left tree
             if(!root->left)
                return  hasPathSum(root->right,sum-root->val);
            
       //For an internal node , we have to check both the left and the right subtree   
              else 
                 return (hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val));
        }

Log in to reply
 

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