Simple C++ solution, recursive dfs, and rewrite nonrecursively with std::stack


  • 0
    Q
    bool hasPathSum(TreeNode* root, int sum) {
    	return !root?false : (sum-=root->val, !root->left && !root->right)? sum==0 : hasPathSum(root->left,sum) || hasPathSum(root->right,sum);
    }
    

    //or

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

    // rewrite nonrecursively with std::stack

    class Solution {
    public:
        bool hasPathSum(TreeNode* root, int sum) {
    		std::stack<TreeNode*> stnr;
    		std::stack<int> stns;
    		if(root) { stnr.push(root); stns.push(sum); }
    		while(!stnr.empty()) {
    		    root=stnr.top(), sum=stns.top()-root->val;
    		    stnr.pop(), stns.pop();
    		    if(!root->left && !root->right) if(sum==0) return true; else continue;
    		    if(root->left) {
    		        if(root->right) { stnr.push(root->right); stns.push(sum); }
    		        stnr.push(root->left); stns.push(sum);
    		    }
    		    else { stnr.push(root->right); stns.push(sum); }
    		}
    		return false;
    	}
    };

Log in to reply
 

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