LeetCode（算法）- 297. 二叉树的序列化与反序列化-阿里云开发者社区

LeetCode（算法）- 297. 二叉树的序列化与反序列化

2022-06-09 91

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode（算法）- 297. 二叉树的序列化与反序列化

题目链接：点击打开链接

题目大意：略

解题思路：略

相关企业

Facebook
亚马逊（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;
    }
};

LeetCode（算法）- 297. 二叉树的序列化与反序列化

热门文章

最新文章

相关课程

相关电子书

相关实验场景