leetcode

commit 624371093e9c6ac8072db39d326e01ff27c86b22
parent a043e9ddc8e8f6c6b258ba0296ebe755197b11ed
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 19 Feb 2023 19:30:45 +0100

Data Structure II: Day 16

Diffstat:
A
Problems/0113.cpp
 | 
26
++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 27 insertions(+), 0 deletions(-)
diff --git a/Problems/0113.cpp b/Problems/0113.cpp
@@ -0,0 +1,26 @@
+class Solution {
+public:
+  vector<vector<int>> pathSum(TreeNode *root, int targetSum) {
+    if (!root) return {};
+    stack<pair<TreeNode *, int>> st;
+    vector<vector<int>> res;
+    vector<int> path;
+    st.push({root, 0});
+    while (!st.empty()) {
+      auto [root, sum] = st.top();
+      if (sum == INT_MIN) {
+        st.pop();
+        path.pop_back();
+        continue;
+      }
+      sum += root->val;
+      st.top().second = INT_MIN;
+      path.push_back(root->val);
+
+      if (!root->left && !root->right && sum == targetSum) res.push_back(path);
+      if (root->left) st.push({root->left, sum});
+      if (root->right) st.push({root->right, sum});
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -104,6 +104,7 @@ for solving problems.
 |  0110  |    Easy    | [Balanced Binary Tree](Problems/0110.cpp)                                                        |
 |  0111  |    Easy    | [Minimum Depth of Binary Tree](Problems/0111.cpp)                                                |
 |  0112  |    Easy    | [Path Sum](Problems/0112.cpp)                                                                    |
+|  0113  |   Medium   | [Path Sum II](Problems/0113.cpp)                                                                 |
 |  0114  |   Medium   | [Flatten Binary Tree to Linked List](Problems/0114.cpp)                                          |
 |  0116  |   Medium   | [Populating Next Right Pointers in Each Node](Problems/0116.cpp)                                 |
 |  0117  |   Medium   | [Populating Next Right Pointers in Each Node II](Problems/0117.cpp)                              |