Recursive way and dfs 14ms and 15ms solution


  • 4
    D
    /*
        bool hasPathSum(TreeNode* root, int sum) {
            if( !root ) 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);
        }
    */
        bool hasPathSum(TreeNode* root, int sum) {
            if( !root ) return false;
            
            stack<pair<TreeNode*,int> > s;
            s.push(make_pair(root, sum));
            int val;
            TreeNode* p;
            
            while( !s.empty() ) {
                p = s.top().first;
                val = s.top().second;
                s.pop();
                if( p->left == NULL && p->right == NULL && p->val == val ) 
                    return true;
                if( p->right ) 
                    s.push(make_pair(p->right, val - p->val));
                if( p->left ) 
                    s.push(make_pair(p->left, val - p->val));
            }
            return false;
        }
    

    Here I present two methods to check if the tree contains the sum :

    a) first it's the recursive -- the most easiest way to do that. we just verify if current node is a leaf and its value equals the sum. If yes, just return true. Others we should check the left tree and right tree in the same way

    b) just like above thinking but with a stack to hold the current needed value and the node.


Log in to reply
 

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