leetcode

commit 5747d61b9b206396e516aeafedfc90598dcc366c
parent a630e067a27b7d4c1b603d92ac2cbb07bbc249cc
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 21 Feb 2023 22:37:09 +0100

Data Structure II: Day 18

Diffstat:
A
Problems/0297.cpp
 | 
41
+++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 42 insertions(+), 0 deletions(-)
diff --git a/Problems/0297.cpp b/Problems/0297.cpp
@@ -0,0 +1,41 @@
+class Codec {
+public:
+  string serialize(TreeNode *root) {
+    ostringstream out;
+    serialize(root, out);
+    return out.str();
+  }
+
+  TreeNode *deserialize(string data) {
+    istringstream in(data);
+    return deserialize(in);
+  }
+
+private:
+  void serialize(TreeNode *root, ostringstream &out) {
+    stack<TreeNode *> st;
+
+    st.push(root);
+    while (!st.empty()) {
+      TreeNode *root = st.top();
+      st.pop();
+      if (!root)
+        out << "# ";
+      else {
+        out << root->val << ' ';
+        st.push(root->right);
+        st.push(root->left);
+      }
+    }
+  }
+
+  TreeNode *deserialize(istringstream &in) {
+    string val;
+    in >> val;
+    if (val == "#") return nullptr;
+    TreeNode *root = new TreeNode(stoi(val));
+    root->left = deserialize(in);
+    root->right = deserialize(in);
+    return root;
+  }
+};
diff --git a/README.md b/README.md
@@ -190,6 +190,7 @@ for solving problems.
 |  0287  |   Medium   | [Find the Duplicate Number](Problems/0287.cpp)                                                   |
 |  0290  |    Easy    | [Word Pattern](Problems/0290.cpp)                                                                |
 |  0295  |    Hard    | [Find Median from Data Stream](Problems/0295.cpp)                                                |
+|  0297  |    Hard    | [Serialize and Deserialize Binary Tree](Problems/0297.cpp)                                       |
 |  0299  |   Medium   | [Bulls and Cows](Problems/0299.cpp)                                                              |
 |  0300  |   Medium   | [Longest Increasing Subsequence](Problems/0300.cpp)                                              |
 |  0304  |   Medium   | [Range Sum Query 2D - Immutable](Problems/0304.cpp)                                              |