16ms C++ by propagating sum all the way to the leaves


  • 0
    B

    Not as elegant as other solution (ones which substract node->val as they descend the tree), but it still works.

    class Solution {
    public:
    
        void propagateSum(TreeNode* root, int sum) {
            if (root == NULL) return;
            root->val += sum;
        
            propagateSum(root->left, root->val);
            propagateSum(root->right, root->val);
        }
        
        bool hasPathSumFromPropagatedTree(TreeNode* root, int sum) {
            if (root == NULL) return false;
        
            // leaf
            if (root->left == NULL &&
                root->right == NULL) {
                return sum == root->val;
            }
        
            return hasPathSumFromPropagatedTree(root->left, sum) ||
                   hasPathSumFromPropagatedTree(root->right, sum);
        }
        
        bool hasPathSum(TreeNode* root, int sum) {
            propagateSum(root, 0);
            return hasPathSumFromPropagatedTree(root, sum);
        }
    

    };


Log in to reply
 

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