leetcode

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 };