题目链接：点击打开链接
题目大意：略
解题思路：略
相关企业
- 亚马逊（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)publicclassCodec { publicStringserialize(TreeNoderoot) { StringBuildersb=newStringBuilder(); Queue<TreeNode>queue=newLinkedList<TreeNode>(){{offer(root);}}; while (!queue.isEmpty()) { TreeNodenode=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); } returnsb.toString(); } publicTreeNodedeserialize(Stringdata) { String[] arr=data.split("#"); intptrPar=arr.length-1, ptrSub=arr.length-1; Map<Integer, TreeNode>nodeMap=newHashMap<>(); Map<TreeNode, TreeNode>parLMap=newHashMap<>(); Map<TreeNode, TreeNode>parRMap=newHashMap<>(); booleanflag=true; while (ptrPar>=0) { // 定位父亲指针while (arr[ptrPar].equals(String.valueOf(Integer.MAX_VALUE))) { ptrPar--; } // 生成父节点TreeNodeparNode=newTreeNode(Integer.valueOf(arr[ptrPar])); nodeMap.put(ptrPar--, parNode); // 生成儿子节点TreeNodelNode, rNode; if (nodeMap.containsKey(ptrSub)) { rNode=nodeMap.get(ptrSub); } else { IntegerarrValue=Integer.valueOf(arr[ptrSub]); rNode=newTreeNode(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 { IntegerarrValue=Integer.valueOf(arr[ptrSub]); lNode=newTreeNode(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); returnnodeMap.get(0); } privatevoidconvertTree(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)publicclassCodec { publicStringserialize(TreeNoderoot) { if(root==null) return"[]"; StringBuilderres=newStringBuilder("["); Queue<TreeNode>queue=newLinkedList<>() {{ add(root); }}; while(!queue.isEmpty()) { TreeNodenode=queue.poll(); if(node!=null) { res.append(node.val+","); queue.add(node.left); queue.add(node.right); } elseres.append("null,"); } res.deleteCharAt(res.length() -1); res.append("]"); returnres.toString(); } publicTreeNodedeserialize(Stringdata) { if(data.equals("[]")) returnnull; String[] vals=data.substring(1, data.length() -1).split(","); TreeNoderoot=newTreeNode(Integer.parseInt(vals[0])); Queue<TreeNode>queue=newLinkedList<>() {{ add(root); }}; inti=1; while(!queue.isEmpty()) { TreeNodenode=queue.poll(); if(!vals[i].equals("null")) { node.left=newTreeNode(Integer.parseInt(vals[i])); queue.add(node.left); } i++; if(!vals[i].equals("null")) { node.right=newTreeNode(Integer.parseInt(vals[i])); queue.add(node.right); } i++; } returnroot; } }
- 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));classCodec { public: // Encodes a tree to a single string.stringserialize(TreeNode*root) { if(root==nullptr) return"[]"; stringres="["; 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); } elseres+="null,"; } res.pop_back(); res+="]"; returnres; } // Decodes your encoded data to tree.TreeNode*deserialize(stringdata) { if (data=="[]") returnnullptr; vector<string>list=split(data.substr(1, data.length() -2), ","); TreeNode*root=newTreeNode(std::stoi(list[0])); queue<TreeNode*>que; que.emplace(root); inti=1; while(!que.empty()) { TreeNode*node=que.front(); que.pop(); if(list[i] !="null") { node->left=newTreeNode(std::stoi(list[i])); que.emplace(node->left); } i++; if(list[i] !="null") { node->right=newTreeNode(std::stoi(list[i])); que.emplace(node->right); } i++; } returnroot; } private: // Split a str by a delimvector<string>split(stringstr, stringdelim) { vector<string>list; inti=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; } returnlist; } };
