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

  • 0

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

    class Solution {
        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.