aboutsummaryrefslogtreecommitdiff
path: root/path_sum.cpp
blob: 41498ca53769d1d9656849788000a7fc8e428f4c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "leetcode.h"

class Solution {
public:
  bool hasPathSum(TreeNode *root, int targetSum) {
    if (root == NULL)
      return false;
    stack<pair<TreeNode *, int>> s;
    s.push({root, root->val});
    while (!s.empty()) {
      TreeNode *curr = s.top().first;
      int total = s.top().second;
      s.pop();
      if (curr->right)
        s.push({curr->right, total + curr->right->val});
      if (curr->left)
        s.push({curr->left, total + curr->left->val});
      if (!curr->right && !curr->left && total == targetSum)
        return true;
    }
    return false;
  }
};