leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0449.cpp (1536B)

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