4-line implementation C++ DFS solution with sum from root as helper (with explanation)


  • 0

    The tree problem is very intuitive to be solved via recursion (just like how a tree is defined recursively).

    Let N(r,s) be the number of paths with sum as s and Nr(r,s) for those paths starting from the root, the recursion idea is straightforward

    • N(r, s) = N(rLeft, s) + N(rRight, s) + Nr(rLeft, s-rVal) + Nr(rRight, s-rVal) + (s==rVal? 1:0),

    where Nr(r,s) also has recursion

    • Nr(r,s) = Nr(rLeft,s-rVal) + Nr(rRight,s-rVal) + (s==rVal? 1:0).

    Both base cases are

    • N(NULL, s) = 0, Nr(NULL, s) = 0.
        int pathSum(TreeNode* r, int sum) {
          if (!r) return 0; int diff = sum-r->val;
          return pathSum(r->left,  sum) + pathSumFromRoot(r->left,  diff) +
                 pathSum(r->right, sum) + pathSumFromRoot(r->right, diff) + (diff? 0 : 1);
        }
        // number of path to sum starting from root
        int pathSumFromRoot(TreeNode* r, int sum) {
          if (!r) return 0; int diff = sum-r->val;
          return pathSumFromRoot(r->left, diff) + pathSumFromRoot(r->right, diff) + (diff? 0 : 1);
        }
    

Log in to reply
 

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