4.Path Sum

Type I

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Given the below binary tree and sum = 22.

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

Recursive Solution:

class Solution
{
public:
    bool hasPathSum(TreeNode *root, int sum)
    {
   
        if (root == NULL)
        {
            return false;
        }

        if (root->left == NULL && root->right == NULL)
        {
            if (root->val == sum)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        
          if(hasPathSum(root->left, sum - root->val)){
                return true;
            }
        
        
           if(hasPathSum(root->right, sum - root->val)){
               return true;
           }
    
        
        return false;
    }
};

Type II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:
[
   [5,4,11,2],
   [5,8,4,5]
]

Solution:

class Solution
{
public:
    
    vector<vector<int>> k;
    vector<int> v;

    void hasPath(TreeNode *root, int sum)
    {

        if (root == NULL)
        {
            return;
        }

        v.push_back(root->val);
        if (root->left == NULL && root->right == NULL)
        {
            if (root->val == sum)
            {
                k.push_back(v);
            }
        }

        hasPath(root->left, sum - root->val);
        hasPath(root->right, sum - root->val);

        v.pop_back();
        return;
    }

    vector<vector<int>> pathSum(TreeNode *root, int sum)
    {

        hasPath(root, sum);
        return k;
    }
};