leetcode

commit 558b26de15c97da88cb6cce6f430348e1100ad84
parent f3d6d1c6a9fd52d28c12847703641ae18970d711
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 16 Mar 2023 23:21:04 +0100

Daily Problem

Diffstat:
A
Problems/0106.cpp
 | 
32
++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 33 insertions(+), 0 deletions(-)
diff --git a/Problems/0106.cpp b/Problems/0106.cpp
@@ -0,0 +1,32 @@
+class Solution {
+  class Record {
+  public:
+    int low, high;
+    TreeNode **field;
+    Record(int l, int h, TreeNode **f) : low(l), high(h), field(f) {}
+  };
+
+public:
+  TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
+    unordered_map<int, int> um;
+    for (int i = 0; i < inorder.size(); i++) um[inorder[i]] = i;
+
+    int crnt = postorder.size() - 1;
+    TreeNode head, *nw;
+    stack<Record> st;
+
+    st.push({0, (int)inorder.size(), &head.right});
+    while (!st.empty()) {
+      Record r = st.top();
+      st.pop();
+      while (r.low < r.high) {
+        int pos = um[postorder[crnt]];
+        nw = *r.field = new TreeNode(postorder[crnt--]);
+        st.push({r.low, pos, &nw->left});
+        r.low = pos + 1;
+        r.field = &nw->right;
+      }
+    }
+    return head.right;
+  }
+};
diff --git a/README.md b/README.md
@@ -103,6 +103,7 @@ for solving problems.
 |  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)                   |
+|  0106  |   Medium   | [Construct Binary Tree from Inorder and Postorder Traversal](Problems/0106.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)                                   |