C++ 2 lines body code (with explanation)


  • 1

    Explanation for helper function f is below. The rest should be self-explanatory.

        class Solution {
        public:
        int pathSum(TreeNode* root, int sum) {
            return root ? f(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum) : 0;
        }
        
        int f(TreeNode* root, int sum) {
            return root ? (root->val == sum) + f(root->left, sum - root->val) + f(root->right, sum - root->val) : 0;
        }
    };
    

    Helper function f(root, sum) = path sum if we only consider paths beginning at root

    For example, for the following tree, f(root, sum=6) is 1 based on path [5, 3, -2].

    Although path [3, 3] also sums to 6, it's not counted because it doesn't begin with root node 5.

        5 
       / \ 
      3   2 
     / \   \
    3  -2   1
    

Log in to reply
 

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