LeetCode_Archiver/LeetCode/cpp/449.cpp at master · chr1sc2y/LeetCode_Archiver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
class Codec {
public:

    vector<int> preorderTraverse(TreeNode *root) {
        if (!root)
            return {};
        vector<int> ret;
        stack<TreeNode *> s;
        s.push(root);
        while (!s.empty()) {
            root = s.top();
            ret.push_back(root->val);
            s.pop();
            if (root->right) s.push(root->right);
            if (root->left) s.push(root->left);
        }
        return ret;
    }

    vector<int> inorderTraverse(TreeNode *root) {
        if (!root)
            return {};
        vector<int> ret;
        stack<TreeNode *> s;
        while (root || !s.empty()) {
            if (root) {
                s.push(root);
                root = root->left;
            } else {
                root = s.top();
                ret.push_back(root->val);
                s.pop();
                root = root->right;
            }
        }
        return ret;
    }


    // Encodes a tree to a single string.
    string serialize(TreeNode *root) {
        string ret;
        vector<int> pre = preorderTraverse(root);
        vector<int> in = inorderTraverse(root);

        for (auto p: pre)
            ret += to_string(p) + ' ';
        ret += '.';
        for (auto i: in)
            ret += to_string(i) + ' ';
        ret += '.';

        return ret;
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data) {
        vector<int> pre;
        vector<int> in;
        int i = 0;
        while (data[i] != '.' && i < data.size()) {
            int temp = 0;
            while (data[i] != ' ') {
                temp = temp * 10 + (data[i] - '0');
                ++i;
            }
            pre.push_back(temp);
            ++i;
        }
        ++i;
        while (data[i] != '.' && i < data.size()) {
            int temp = 0;
            while (data[i] != ' ') {
                temp = temp * 10 + (data[i] - '0');
                ++i;
            }
            in.push_back(temp);
            ++i;
        }

        return BuildTree(pre, 0, pre.size() - 1, in, 0, in.size() - 1);
    }

    TreeNode *BuildTree(vector<int> &pre, int i, int j, vector<int> &in, int m, int n) {
        if (i > j || m > n)
            return nullptr;
        auto root = new TreeNode(pre[i]);
        int x = m, y = n, index = (x + y) / 2;
        while (x <= y) {
            index = (x + y) / 2;
            if (in[index] == pre[i])
                break;
            else if (in[index] > pre[i])
                y = index - 1;
            else
                x = index + 1;
        }
        root->left = BuildTree(pre, i + 1, i + (index - m), in, m, index - 1);
        root->right = BuildTree(pre, i + (index - m) + 1, j, in, index + 1, n);
        return root;
    }

};