jz37.序列换二叉树

题目描述

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

示例:

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

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

题解

BFS

这道题要求实现两个方法, 一个是层序遍历将一个二叉树序列化, 还要根据已知的序列化字符串还原出原二叉树.

首先先来解决序列化问题:

序列化

这个序列化问题与之前的各种BFS问题一样, 无非就是需要把null 也打印出来, 并且最终结果生成字符串的形式. 字符串形式好说, 直接利用列表的toString() 方法即可. 下面主要来讨论如何把null 打印出来.

之前的BFS过程中, 都有这么一个步骤:

if (temp.left != null)
    queue.add(temp.left);
if (temp.right != null)
    queue.add(temp.right);

这么写是为了不让null 入队, 而这道题我们需要将null 入队, 所以两个判断句省去.

另外, 判断一下如果当前出队的节点为null, 则向列表中加入null , 不再考虑null 的左右子节点.

// Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res.toString();
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            if (temp != null) {
                res.add(temp.val);
                queue.add(temp.left);
                queue.add(temp.right);
            } else {
                res.add(null);
            }
        }

        return res.toString();
    }

反序列化

给定一个包含null 的字符串, 将它还原成一个完整二叉树. 这就要分析层序遍历中各节点元素的顺序关系了

直接看图解:

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if (data.equals("[]")) return null;
    String[] strings = data.substring(1, data.length() - 1).split(", ");
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode root = new TreeNode(Integer.parseInt(strings[0]));
    queue.add(root);
    int i = 1;

    while (!queue.isEmpty()) {
        TreeNode temp = queue.poll();

        if (!strings[i].equals("null")) {
            temp.left = new TreeNode(Integer.parseInt(strings[i]));
            queue.add(temp.left);
        }
        i++;

        if (!strings[i].equals("null")) {
            temp.right = new TreeNode(Integer.parseInt(strings[i]));
            queue.add(temp.right);
        }
        i++;

    }
    return root;
}