A 7ms C solution


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

    If the root node is a leaf, check if it satisfies our condition (sum - root->val == 0). If the root node is not a leaf, subtract its value from sum and return whether either of its children satisfy that same condition.


  • 0
    R

    It can be optimized to 4 ms =)

    bool hasPathSum(struct TreeNode* root, int sum) {
    if (!root)
    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
    R
    bool hasPathSum(struct TreeNode* root, int sum) {
    	if(NULL==root) return false;
    
    	if(NULL==root->left && NULL==root->right){
    		return sum==root->val;
    	}
    	sum-=root->val;
        
    	return hasPathSum(root->left,sum)||hasPathSum(root->right,sum);
    }
    

    simple neat version of DFS, make reading easier~


Log in to reply
 

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