297. 二叉树的序列化与反序列化 (opens new window)

1.队列

解题思路：编码采用先序遍历保存二叉树。解题关键在于如何通过二叉树的“先序序列”生成构建二叉树。

⚡⚡⚡这里的序列并不等同于先序遍历序列，对于每个叶子节点空孩子节点也会保存进当前序列当中。因此该序列有一个很关键的性质，只要队列中当前节点不为空，那么下一个节点一定是它的左子树节点。(正常的前中后二叉树遍历序列至少需要同时知道两个才能够构建一棵唯一的二叉树)

采用队列保存二叉树，如果队列元素不为空，那么就需要继续递归遍历生成元素(跟序列化操作保持一致)，如果为空说明当前节点的子节点为空。具体流程如下：

• 构建左子树，判断队列队首元素
  • 如果为空则构建右子树
  • 如果不为空则生成左子树节点，并递归搜索左子树
• 构建右子树
  • 如果为空，说明当前节点左右子树构建完毕，退出循环。
  • 如果不为空，生成右子树，并递归搜索右子树

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder s=new StringBuilder();
        dfs(root,s);
        return s.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] str=data.split(",");
        List<String> list=new ArrayList<>(Arrays.asList(str));
        TreeNode root=str[0].equals("null")?null:new TreeNode(Integer.valueOf(str[0]));
        list.remove(0);
        build(root,list);      
        return root;

    }
    public void dfs(TreeNode root,StringBuilder s){
        if(root==null){
            s.append("null,");
            return ;
        }
        s.append(String.valueOf(root.val)+",");
        dfs(root.left,s);
        dfs(root.right,s);
    }
    public void build(TreeNode root, List<String> list){
        if(list.size()==0) return ;
        if(list.get(0).equals("null")){
            root.left=null;
            list.remove(0);
        }else{
            root.left=new TreeNode(Integer.valueOf(list.get(0)));
            list.remove(0);
            build(root.left,list);
        }
        if(list.get(0).equals("null")){
            root.right=null;
            list.remove(0);
        }else{
            root.right=new TreeNode(Integer.valueOf(list.get(0)));
            list.remove(0);
            build(root.right,list);
        }
        return;
       
    }
}

2.数组存储二叉树

😭😭😭数组索引爆了没过，仅分享思路

• 解题思路

使用一维数组存储二叉树，核心是通过索引下标来找到当前节点的左右孩子节点，不需要在字符串中另外存储二叉树的结构。

对于一个索引下标为i节点，它的左子树的索引为2*i+1，右子树的索引为2*i+2。

• 问题

对于非平衡的二叉树，例如一棵只有右孩子的非常不平衡的二叉树，树的层数每增加一层，索引下标呈指数级别增长，容易导致索引数值溢出范围爆了。从而在序列化中没有保存上对应节点信息。

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder s=new StringBuilder();
        dfs(root,s,0);
        return s.toString();
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] str=data.split("!");
        HashMap<Integer,String> map=new HashMap<>();
        for(int i=0;i<str.length;i++){
            String s=str[i];
            String[] split=s.split(",");
            if(split.length==1){
                map.put(Integer.valueOf(split[0]),"null");
            }else {
                map.put(Integer.valueOf(split[0]),split[1]);
            }
        }
        TreeNode root=map.get(0).equals("null")?null:new TreeNode(Integer.valueOf(map.get(0)));
        build(root,map,0);
        return root;

    }
    public void dfs(TreeNode root,StringBuilder s,int i){
        if(root==null){
            s.append(String.valueOf(i)+",!");
            return ;
        }
        s.append(String.valueOf(i)+","+String.valueOf(root.val)+"!");
        dfs(root.left,s,2*i+1);
        dfs(root.right,s,2*i+2);
    }
    public void build(TreeNode root,HashMap<Integer,String> map,int index){
        if(map.containsKey(index*2+1)&&!map.get(index*2+1).equals("null")){
            String val=map.get(index*2+1);
            root.left=new TreeNode(Integer.valueOf(val));
            build(root.left,map,index*2+1);
        }
        if(map.containsKey(index*2+2)&&!map.get(index*2+2).equals("null")){
            String val=map.get(index*2+2);
            root.right=new TreeNode(Integer.valueOf(val));
            build(root.right,map,index*2+2);
        }
    }
}