美文网首页
37-序列化二叉树

37-序列化二叉树

作者: 一方乌鸦 | 来源:发表于2020-05-06 09:14 被阅读0次

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

    示例:

    你可以将以下二叉树:

        1
       / \
      2   3
         / \
        4   5
    序列化为 "[1,2,3,null,null,4,5]"
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) return "null";
            StringBuilder sb = new StringBuilder();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode node = queue.poll();
                if (node != null) {
                    sb.append(String.valueOf(node.val)).append(",");
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else {
                    sb.append("null").append(",");
                }
            }
            sb.setLength(sb.length() - 1);
            return sb.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.equals("null")) return null;
            String[] s = data.split(",");
            TreeNode head = new TreeNode(Integer.valueOf(s[0]));
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(head);
            int i = 1;
            while(!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (i < s.length && !s[i].equals( "null")) {
                    node.left = new TreeNode(Integer.valueOf(s[i]));
                    queue.offer(node.left);
                }
                i++;
                if (i < s.length && !s[i].equals( "null")) {
                    node.right = new TreeNode(Integer.valueOf(s[i]));
                    queue.offer(node.right);
                }
                i++;
            }
            return head;
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));
    

    相关文章

      网友评论

          本文标题:37-序列化二叉树

          本文链接:https://www.haomeiwen.com/subject/ooxdghtx.html