leetcode

commit 30cb3fa1b382e513024b3f6c934a0f7d9fbbddd2
parent 5c32b2fa0cd72bc58ac2cd561385f566a835f328
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 10 Feb 2023 15:55:36 +0100

LeetCode 75 II: Day 7

Diffstat:
A
Problems/0437.cpp
 | 
70
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 71 insertions(+), 0 deletions(-)
diff --git a/Problems/0437.cpp b/Problems/0437.cpp
@@ -0,0 +1,70 @@
+// Brute force
+class Solution {
+public:
+  int pathSum(TreeNode *root, int targetSum) {
+    if (!root) return 0;
+
+    stack<TreeNode *> st;
+    queue<TreeNode *> q;
+
+    st.push(root);
+    while (!st.empty()) {
+      TreeNode *root = st.top();
+      st.pop();
+      q.push(root);
+      if (root->left) st.push(root->left);
+      if (root->right) st.push(root->right);
+    }
+
+    int res = 0;
+    while (!q.empty()) {
+      stack<pair<TreeNode *, long long>> st;
+      st.push({q.front(), 0});
+      q.pop();
+      while (!st.empty()) {
+        auto [root, sum] = st.top();
+        st.pop();
+        sum += root->val;
+        if (sum == targetSum) res++;
+        if (root->left) st.push({root->left, sum});
+        if (root->right) st.push({root->right, sum});
+      }
+    }
+
+    return res;
+  }
+};
+
+// Optimized
+class Solution {
+public:
+  int pathSum(TreeNode *root, int targetSum) {
+    if (!root) return 0;
+    queue<pair<TreeNode *, vector<long long>>> q;
+    int res = 0;
+
+    q.push({root, {}});
+    while (!q.empty()) {
+      auto &[root, vec] = q.front();
+      long long sum = root->val + (vec.size() ? vec.back() : 0);
+
+      for (int num : vec)
+        if (sum - num == targetSum) res++;
+      if (sum == targetSum) res++;
+
+      if (root->left) {
+        q.push({root->left, vec});
+        q.back().second.push_back(sum);
+      }
+
+      if (root->right) {
+        q.push({root->right, vec});
+        q.back().second.push_back(sum);
+      }
+
+      q.pop();
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -209,6 +209,7 @@ for solving problems.
 |  0430  |   Medium   | [Flatten a Multilevel Doubly Linked list](Problems/0430.cpp)                                     |
 |  0433  |   Medium   | [Minimum Genetic Mutation](Problems/0433.cpp)                                                    |
 |  0435  |   Medium   | [Non-overlapping Intervals](Problems/0435.cpp)                                                   |
+|  0437  |   Medium   | [Path Sum III](Problems/0437.cpp)                                                                |
 |  0438  |   Medium   | [Find All Anagrams in a String](Problems/0438.cpp)                                               |
 |  0445  |   Medium   | [Add Two Numbers II](Problems/0445.cpp)                                                          |
 |  0448  |    Easy    | [Find All Numbers Disappeared in an Array](Problems/0448.cpp)                                    |