题目链接：点击打开链接
题目大意：略
解题思路：略
相关企业
- 亚马逊（Amazon）
- 微软（Microsoft）
- 谷歌（Google）
- 英伟达（NVIDIA）
- 优步（Uber）
- 苹果（Apple）
- 甲骨文（Oracle）
AC 代码
- Java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // Your Codec object will be instantiated and called as such: // Codec ser = new Codec(); // Codec deser = new Codec(); // TreeNode ans = deser.deserialize(ser.serialize(root)); // 解决方案(1) public class Codec { public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); Queue<TreeNode> queue = new LinkedList<TreeNode>(){{offer(root);}}; while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node == null) { sb.append(Integer.MAX_VALUE).append("#"); continue; } sb.append(node.val).append("#"); queue.offer(node.left); queue.offer(node.right); } return sb.toString(); } public TreeNode deserialize(String data) { String[] arr = data.split("#"); int ptrPar = arr.length - 1, ptrSub = arr.length - 1; Map<Integer, TreeNode> nodeMap = new HashMap<>(); Map<TreeNode, TreeNode> parLMap = new HashMap<>(); Map<TreeNode, TreeNode> parRMap = new HashMap<>(); boolean flag = true; while (ptrPar >= 0) { // 定位父亲指针 while (arr[ptrPar].equals(String.valueOf(Integer.MAX_VALUE))) { ptrPar--; } // 生成父节点 TreeNode parNode = new TreeNode(Integer.valueOf(arr[ptrPar])); nodeMap.put(ptrPar--, parNode); // 生成儿子节点 TreeNode lNode, rNode; if (nodeMap.containsKey(ptrSub)) { rNode = nodeMap.get(ptrSub); } else { Integer arrValue = Integer.valueOf(arr[ptrSub]); rNode = new TreeNode(arrValue); if (!arrValue.equals(Integer.MAX_VALUE)) { flag = false; } if (flag) { parRMap.put(rNode, parNode); } } ptrSub--; if (nodeMap.containsKey(ptrSub)) { lNode = nodeMap.get(ptrSub); } else { Integer arrValue = Integer.valueOf(arr[ptrSub]); lNode = new TreeNode(arrValue); if (!arrValue.equals(Integer.MAX_VALUE)) { flag = false; } if (flag) { parLMap.put(lNode, parNode); } } ptrSub--; // 组合节点 parNode.right = rNode; parNode.left = lNode; } // 满二叉树转换完全二叉树(去除末尾的 NULL) convertTree(parLMap, parRMap); return nodeMap.get(0); } private void convertTree(Map<TreeNode, TreeNode> parLMap, Map<TreeNode, TreeNode> parRMap) { for (Map.Entry<TreeNode, TreeNode> item : parLMap.entrySet()) { item.getValue().left = null; } for (Map.Entry<TreeNode, TreeNode> item : parRMap.entrySet()) { item.getValue().right = null; } } } // 解决方案(2) public class Codec { public String serialize(TreeNode root) { if(root == null) return "[]"; StringBuilder res = new StringBuilder("["); Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }}; while(!queue.isEmpty()) { TreeNode node = queue.poll(); if(node != null) { res.append(node.val + ","); queue.add(node.left); queue.add(node.right); } else res.append("null,"); } res.deleteCharAt(res.length() - 1); res.append("]"); return res.toString(); } public TreeNode deserialize(String data) { if(data.equals("[]")) return null; String[] vals = data.substring(1, data.length() - 1).split(","); TreeNode root = new TreeNode(Integer.parseInt(vals[0])); Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }}; int i = 1; while(!queue.isEmpty()) { TreeNode node = queue.poll(); if(!vals[i].equals("null")) { node.left = new TreeNode(Integer.parseInt(vals[i])); queue.add(node.left); } i++; if(!vals[i].equals("null")) { node.right = new TreeNode(Integer.parseInt(vals[i])); queue.add(node.right); } i++; } return root; } }
- C++
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ // Your Codec object will be instantiated and called as such: // Codec ser, deser; // TreeNode* ans = deser.deserialize(ser.serialize(root)); class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { if(root == nullptr) return "[]"; string res = "["; queue<TreeNode*> que; que.emplace(root); while(!que.empty()) { TreeNode* node = que.front(); que.pop(); if(node != nullptr) { res += (to_string(node->val) + ","); que.emplace(node->left); que.emplace(node->right); } else res += "null,"; } res.pop_back(); res += "]"; return res; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { if (data == "[]") return nullptr; vector<string> list = split(data.substr(1, data.length() - 2), ","); TreeNode *root = new TreeNode(std::stoi(list[0])); queue<TreeNode*> que; que.emplace(root); int i = 1; while(!que.empty()) { TreeNode *node = que.front(); que.pop(); if(list[i] != "null") { node->left = new TreeNode(std::stoi(list[i])); que.emplace(node->left); } i++; if(list[i] != "null") { node->right = new TreeNode(std::stoi(list[i])); que.emplace(node->right); } i++; } return root; } private: // Split a str by a delim vector<string> split(string str, string delim) { vector<string> list; int i = 0, j = 0, len = str.length(); while (i < len) { while (j < len && str[j] != ',') j++; list.push_back(str.substr(i, j - i)); i = ++j; } return list; } };
