leetcode

commit a043e9ddc8e8f6c6b258ba0296ebe755197b11ed
parent ed18bdfd7d9428d3d92bbd14a2adaea517d1b87c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 18 Feb 2023 20:38:59 +0100

Data Structure II: Day 15

Diffstat:
A
Problems/0105.cpp
 | 
31
+++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 32 insertions(+), 0 deletions(-)
diff --git a/Problems/0105.cpp b/Problems/0105.cpp
@@ -0,0 +1,31 @@
+class Solution {
+  typedef vector<int>::iterator vii;
+  struct Record {
+    TreeNode **fill = nullptr;
+    vii start, end;
+    Record(TreeNode **f, vii s, vii e) : fill(f), start(s), end(e) {}
+  };
+
+public:
+  TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
+    stack<Record> st;
+    TreeNode head;
+    int pre = 0;
+
+    st.push({&head.right, inorder.begin(), inorder.end()});
+    while (!st.empty()) {
+      Record r = st.top();
+      st.pop();
+      while (r.start < r.end) {
+        vii mid = find(r.start, r.end, preorder[pre]);
+        if (mid == r.end) break;
+        TreeNode *n = *r.fill = new TreeNode(preorder[pre++]);
+        st.push({&n->right, next(mid), r.end});
+        r.end = mid;
+        r.fill = &n->left;
+      }
+    }
+
+    return head.right;
+  }
+};
diff --git a/README.md b/README.md
@@ -97,6 +97,7 @@ for solving problems.
 |  0102  |   Medium   | [Binary Tree Level Order Traversal](Problems/0102.cpp)                                           |
 |  0103  |   Medium   | [Binary Tree Zigzag Level Order Traversal](Problems/0103.cpp)                                    |
 |  0104  |    Easy    | [Maximum Depth of Binary Tree](Problems/0104.cpp)                                                |
+|  0105  |   Medium   | [Construct Binary Tree from Preorder and Inorder Traversal](Problems/0105.cpp)                   |
 |  0107  |   Medium   | [Binary Tree Level Order Traversal II](Problems/0107.cpp)                                        |
 |  0108  |    Easy    | [Convert Sorted Array to Binary Search Tree](Problems/0108.cpp)                                  |
 |  0109  |   Medium   | [Convert Sorted List to Binary Search Tree](Problems/0109.cpp)                                   |