leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0437.cpp (1778B)

      1 // Brute force
      2 class Solution {
      3   public:
      4     int pathSum(TreeNode *root, int targetSum) {
      5         if (!root) return 0;
      6 
      7         stack<TreeNode *> st;
      8         queue<TreeNode *> q;
      9 
     10         st.push(root);
     11         while (!st.empty()) {
     12             TreeNode *root = st.top();
     13             st.pop();
     14             q.push(root);
     15             if (root->left) st.push(root->left);
     16             if (root->right) st.push(root->right);
     17         }
     18 
     19         int res = 0;
     20         while (!q.empty()) {
     21             stack<pair<TreeNode *, long long>> st;
     22             st.push({q.front(), 0});
     23             q.pop();
     24             while (!st.empty()) {
     25                 auto [root, sum] = st.top();
     26                 st.pop();
     27                 sum += root->val;
     28                 if (sum == targetSum) res++;
     29                 if (root->left) st.push({root->left, sum});
     30                 if (root->right) st.push({root->right, sum});
     31             }
     32         }
     33 
     34         return res;
     35     }
     36 };
     37 
     38 // Optimized
     39 class Solution {
     40   public:
     41     int pathSum(TreeNode *root, int targetSum) {
     42         if (!root) return 0;
     43         queue<pair<TreeNode *, vector<long long>>> q;
     44         int res = 0;
     45 
     46         q.push({root, {}});
     47         while (!q.empty()) {
     48             auto &[root, vec] = q.front();
     49             long long sum = root->val + (vec.size() ? vec.back() : 0);
     50 
     51             for (int num : vec)
     52                 if (sum - num == targetSum) res++;
     53             if (sum == targetSum) res++;
     54 
     55             if (root->left) {
     56                 q.push({root->left, vec});
     57                 q.back().second.push_back(sum);
     58             }
     59 
     60             if (root->right) {
     61                 q.push({root->right, vec});
     62                 q.back().second.push_back(sum);
     63             }
     64 
     65             q.pop();
     66         }
     67 
     68         return res;
     69     }
     70 };