龙空技术网

序列化二叉树

解夏126 55

前言:

眼前我们对“java二叉树序列化”大约比较着重,我们都需要剖析一些“java二叉树序列化”的相关资讯。那么小编同时在网络上汇集了一些对于“java二叉树序列化””的相关文章,希望咱们能喜欢,同学们快快来了解一下吧!

序列化二叉树

请实现两个函数,分别用来序列化和反序列化二叉树。

您需要确保二叉树可以序列化为字符串,并且可以将此字符串反序列化为原始树结构。

注意:

以上的格式是AcWing序列化二叉树的方式,你不必一定按照此格式,所以可以设计出一些新的构造方式。

样例你可以序列化如下的二叉树    8   / \  12  2     / \    6   4为:"[8, 12, 2, null, null, 6, 4, null, null, null, null]"
队列

时间复杂度O(n)

class Solution {    // Encodes a tree to a single string.    String serialize(TreeNode root) {        Queue que = new LinkedList();        if(root == null){            return "#!";        }        String res = root.val + "!";        que.offer(root);        while(que.peek() != null){            TreeNode tr = (TreeNode)que.poll();            if(tr.left != null){                que.offer(tr.left);                res += tr.left.val + "!";            }else{                res += "#!";            }            if(tr.right != null){                que.offer(tr.right);                res += tr.right.val + "!";            }else{                res += "#!";            }        }        return res;    }    // Decodes your encoded data to tree.    TreeNode deserialize(String data) {        Queue qu = new LinkedList();        String[] da = data.split("!");        if("#".equals(da[0])){            return null;        }        TreeNode tt = new TreeNode(Integer.parseInt(da[0]));        TreeNode temp = tt;        int index = 1;        boolean flag = true;        qu.offer(temp);        TreeNode node = null;        while(qu.peek() != null){            node = (TreeNode)qu.poll();            if(da[index].equals("#")){                node.left = null;            }else{                TreeNode rr = new TreeNode(Integer.parseInt(da[index]));                node.left = rr;                qu.offer(node.left);            }            index++;            if(da[index].equals("#")){                node.right = null;            }else{                TreeNode rr = new TreeNode(Integer.parseInt(da[index]));                node.right = rr;                qu.offer(node.right);            }            index++;        }        return tt;    }}

标签: #java二叉树序列化