leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0449.cpp (1536B)

0 static const auto _ = []() { 1 ios_base::sync_with_stdio(0); 2 cin.tie(NULL); 3 cout.tie(NULL); 4 return NULL; 5 }(); 6 7 class Codec { 8 typedef tuple<TreeNode **, int, int> record; 9 10 public: 11 // Encodes a tree to a single string. 12 string serialize(const TreeNode *root) const { 13 static int buff[10001]; 14 int idx = 0; 15 16 if (!root) return ""; 17 18 stack<const TreeNode *> st; 19 for (st.push(root); !st.empty();) { 20 auto root = st.top(); 21 st.pop(); 22 while (root) { 23 buff[idx++] = root->val; 24 if (root->right) st.push(root->right); 25 root = root->left; 26 } 27 } 28 29 return string(reinterpret_cast<const char *>(buff), idx * 4); 30 } 31 32 // Decodes your encoded data to tree. 33 TreeNode *deserialize(const string &sdata) const { 34 auto data = reinterpret_cast<const int *>(sdata.data()); 35 TreeNode dummy, *node; 36 stack<record> st; 37 38 for (st.push({&dummy.left, 0, size(sdata) / 4}); !st.empty();) { 39 auto [place, start, end] = st.top(); 40 st.pop(); 41 while (start != end) { 42 node = *place = new TreeNode(data[start]); 43 44 const auto mid = upper_bound(data + start, data + end, data[start]) - data; 45 st.push({&node->right, mid, end}); 46 47 place = &node->left; 48 start = start + 1; 49 end = mid; 50 } 51 } 52 53 return dummy.left; 54 } 55 };