遍歷BFSDFS 二叉樹的序列化與反序列化

題目

難度：困難

序列化是將一個數(shù)據(jù)結(jié)構(gòu)或者對象轉(zhuǎn)換為連續(xù)的比特位的操作，進而可以將轉(zhuǎn)換后的數(shù)據(jù)存儲在一個文件或者內(nèi)存中，同時也可以通過網(wǎng)絡傳輸?shù)搅硪粋€計算機環(huán)境，采取相反方式重構(gòu)得到原數(shù)據(jù)。

請設計一個算法來實現(xiàn)二叉樹的序列化與反序列化。這里不限定你的序列 / 反序列化算法執(zhí)行邏輯，你只需要保證一個二叉樹可以被序列化為一個字符串并且將這個字符串反序列化為原始的樹結(jié)構(gòu)。

示例:

你可以將以下二叉樹：

   1
   / \
  2   3
     / \
    4   5


序列化為 "[1,2,3,null,null,4,5]"

解法一：dfs解法

深度優(yōu)先搜索算法（Depth First Search，簡稱DFS）

1.解題

序列化：求二叉樹的先序遍歷序列 反序列化：通過序列化得到的先序遍歷序列 構(gòu)建原二叉樹

public class Codec {


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


    StringBuilder mySeri(TreeNode root,StringBuilder sb){
        if(root==null){
            sb.append("null,");
            return sb;
        }
        else if(root!=null){
            sb.append(root.val);
            sb.append(",");
            mySeri(root.left,sb);
            mySeri(root.right,sb);
        }
        return sb;
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String []temp=data.split(","); // 將序列化的結(jié)果轉(zhuǎn)為字符串數(shù)組
        List<String> list=new LinkedList<>(Arrays.asList(temp)); // 字符串數(shù)組轉(zhuǎn)為集合類 便于操作
        return myDeSeri(list);
    }
    public TreeNode myDeSeri(List<String> list){
        TreeNode root;
        if(list.get(0).equals("null")){
            list.remove(0); // 刪除第一個元素 則第二個元素成為新的首部 便于遞歸 
            return null;
        }
        else{
            root=new TreeNode(Integer.valueOf(list.get(0)));
            list.remove(0);
            root.left=myDeSeri(list);
            root.right=myDeSeri(list);
        }
        return root;
    }
}

2.方法解釋

1.spilt(); 拆分String為字符串數(shù)組 2.Arrays.asList();

（1）該方法不適用于基本數(shù)據(jù)類型（byte,short,int,long,float,double,boolean） （2）該方法將數(shù)組與列表鏈接起來，當更新其中之一時，另一個自動更新 （3）不支持add和remove方法 （1）該方法不適用于基本數(shù)據(jù)類型（byte,short,int,long,float,double,boolean） 　?。?）該方法將數(shù)組與列表鏈接起來，當更新其中之一時，另一個自動更新 　?。?）不支持add和remove方法

解法二：bfs解法

BFS，其英文全稱是Breadth First Search。 寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。

1.解法

序列化：通用bfs 反序列化：每次遍歷2個節(jié)點 這2個節(jié)點是出隊節(jié)點的左右孩子

public class Codec {


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null){
            return "";
        }
        StringBuilder res=new StringBuilder();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur==null){
                res.append("null,");
            }
            else{
               res.append(String.valueOf(cur.val));
               res.append(",");
               queue.offer(cur.left);
               queue.offer(cur.right);
            }
        }

        
        return res.toString();



        
    }




    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("")){
            return null;
        }
        String []temp=data.split(",");
        TreeNode root=new TreeNode(Integer.valueOf(temp[0]));
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        TreeNode cur=root;

        
        for(int i=1;i<temp.length;){
            cur=queue.poll();
            if(!temp[i].equals("null")){
                cur.left=new TreeNode(Integer.valueOf(temp[i]));
                queue.offer(cur.left);


            }
            i+=1;
            if(!temp[i].equals("null")){
                cur.right=new TreeNode(Integer.valueOf(temp[i]));
                queue.offer(cur.right);
            }
            i+=1;
        }
        return root;
    }
}

2.方法解析

1.offer(); 往隊列尾部插入元素，如果超出邊界則返回false

深度優(yōu)先與廣度優(yōu)先的差異

稀疏圖bfs會快于dfs，稠密圖差不多。dfs寫比較簡單，bfs沒有棧溢出風險

1.DFS：棧（先進后出） 走到盡頭 步驟：

1.首先A入棧，

                
2、A出棧時，A的鄰接結(jié)點B，C相應入棧  （這里假設C在下，B在上）


3.B出棧時，B的鄰接結(jié)點A，C，D中未進過棧的D入棧


4.D出棧時，D的鄰接結(jié)點B，C，E，F(xiàn)中未進過棧的E、F入棧（假設E在下，F(xiàn)在上）


5.F出棧時，F(xiàn)沒有鄰接結(jié)點可入棧


6.E出棧，E的鄰接結(jié)點C，D已入過棧


7.C出棧

2.BFS： 隊列（先進先出） 按照層次來遍歷 步驟：

1.首先A入隊列，


2.A出隊列時，A的鄰接結(jié)點B，C相應進入隊列 


3.B出隊列時，B的鄰接結(jié)點A，C，D中未進過隊列的D進入隊列


4.C出隊列時，C的鄰接結(jié)點A，B，D，E中未進過隊列的E進入隊列


5.D出隊列時，D的鄰接結(jié)點B，C，E，F(xiàn)中未進過隊列的F進入隊列


6.E出隊列，沒有結(jié)點可再進隊列


7.F出隊列