[recommend for beginners]recursive & non-recursive C++ implementation with detailed explaination


  • 3
    class Solution {
    public:
        /*** recursive solution  ***/
        bool hasPathSum(TreeNode* root, int sum) {
            if(root==NULL)  return false;
            if(root->left==NULL && root->right==NULL)   return sum==root->val;
            return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
        }
        
        /*** level-bfs-iterative solution  ***/
        bool hasPathSum(TreeNode* root, int sum){
            if(root==NULL)  return false;
            
            queue<TreeNode*> q;
            q.push(root);
            while(q.size()>0){
                TreeNode* node=q.front();
                q.pop();
                if(node->left==NULL && node->right==NULL){
                    if(node->val==sum)  return true;
                }
                if(node->left){
                    node->left->val+=node->val;
                    q.push(node->left);
                }
                if(node->right){
                    node->right->val+=node->val;
                    q.push(node->right);
                }
            }
            return false;
        }
    };

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

Log in to reply
 

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