// Decodes your encoded data to tree. TreeNode* deserialize(string data){ TreeNode* root; vector<int> arr; transArr(data, arr); if(arr.size() == 0) { root = NULL; return root; } // int n = arr.size(); // root->val = arr[n - 1]; root = dfs(arr); return root; }
voidtransArr(string data, vector<int> &arr){ // 将string 拆分为整数数组 int npc = 0; for(int i = 0; i < data.size(); i++){ if(i == data.size() - 1){ string str = data.substr(npc, i - npc + 1); arr.emplace_back(stoi(str)); npc = i + 1; } elseif(data[i] == ','){ string str = data.substr(npc, i - npc); arr.emplace_back(stoi(str)); npc = i + 1; } } } TreeNode* dfs(vector<int> arr){ if(arr.size() == 0){ returnNULL; } int n = arr.size(); int npc = arr[n - 1]; TreeNode* root = newTreeNode(npc); if(n == 1) return root;
int x = find(arr, npc); // 寻找最后一个小于 根节点的下标,则x左边的都是该节点的左子树,右边的都是该节点的右子树 if(x >= 0){ root->left = dfs(vector<int>(arr.begin(), arr.begin() + x)); } if(x <= n - 2){ root-> right = dfs(vector<int>(arr.begin() + x, arr.begin() + n - 1)); } return root; }
intfind(vector<int> arr, int x){ for(int i = 0; i < arr.size() - 1; i ++){ if(arr[i] > x){ return i; } } return arr.size() - 1; } };
// Your Codec object will be instantiated and called as such: // Codec* ser = new Codec(); // Codec* deser = new Codec(); // string tree = ser->serialize(root); // TreeNode* ans = deser->deserialize(tree); // return ans;
时间复杂度:O(n),其中 n 是树的节点个数,serialize 需要 O(n) 时间遍历每个点。deserialize 需要 O(n) 时间恢复每个点