Easy to understand 26ms C++ solution No map or vector


  • 1
    C

    Since we need to find out the total number of paths that add up to sum, we just need to pass the original sum or sum - root->val to the next level. If the sum that passed from the parent equals to the current root->val, then add count by one.

    The tricky part is, you need to use a boolean has_head variable to keep track whether or not the current node can be a new head or not. For example, the total sum is 8, root value is 3, in this case, you can pass either 8 or 5 to the next level. When you pass 8 to the children, it means that its children can be the new head because root is not in the path in this case. When you pass 5 to the children, then the children cannot be the new head anymore because in this case, root is the head. That's why you need the has_head variable so you know if the current node can be head or not with the given sum value.

    class Solution {
    public:
        void countPath(TreeNode* root, int sum, int& count, bool has_head){
            if (!root) return;
            if (root->val==sum) count++;
            if (!has_head){  //in this case current node can be new head
                countPath(root->left, sum, count, false); 
                countPath(root->right, sum, count, false);
            }
            countPath(root->left, sum-root->val, count, true);
            countPath(root->right, sum-root->val, count, true);
        }
        int pathSum(TreeNode* root, int sum) {
            int count = 0;
            countPath(root, sum, count, false);
            return count;
        }
    };
    

  • 1
    C

    @cherrywbtc your code is much cleaner than your explanation, lol!


Log in to reply
 

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