[Leetcode 112] Path Sum

Description:
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

Using C++

Setups:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        //code section
}

Recursive method:

 int restSum;
 if(root == nullptr)
     return false;
 else
     restSum = targetSum — root->val;
 if(root->left == nullptr && root->right == nullptr)
 {
     if(restSum == 0)
         return true;
     else
         return false;
 }
 else
     return hasPathSum(root->left, restSum) || hasPathSum(root->right, restSum);

Iterative method:

// preorder
if(root == nullptr)
    return false;
std::vector<TreeNode*> stack;
std::map<TreeNode*, int> done;
stack.push_back(root);
while(!stack.empty())
{
    TreeNode* node = stack.back();
    if(done.count(node) != 0)
    {
        targetSum += node->val;
        stack.pop_back();
    }
    else
    {
        targetSum -= node->val;
    }
            
    if(node->left == nullptr && node->right == nullptr)
    {
        if(targetSum == 0)
            return true;
        targetSum += node->val;
        stack.pop_back();
    }
    //traverse
    if(done.count(node) == 0)
    {
        if(node->right != nullptr)
        {
            stack.push_back(node->right);
            done[node]++;
        }
        if(node->left != nullptr)
        {
            stack.push_back(node->left);
            done[node]++;
        }
    }
}
return false;