博客

思想

递归, 暴搜

题目

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

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

数据范围

树中节点数量 [0,1000]

。

样例

你可以序列化如下的二叉树

8

/

12 2

/

6 4

为：”[8, 12, 2, null, null, 6, 4, null, null, null, null]”

注意:

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

java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    int index = -1;
    // Encodes a tree to a single string.
    String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root==null) {
            sb.append("null,");
            return sb.toString();
        }

        sb.append(root.val).append(",");
        sb.append(serialize(root.left));
        sb.append(serialize(root.right));
        
        // System.out.println(sb.toString());
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    TreeNode deserialize(String data) {
        index++;
        String[] nodes = data.split(",");
        
        // for (int i = 0; i < nodes.length; i++) {
        //     System.out.println(nodes[i]);
        // }
        
        TreeNode node = null;
        if(!nodes[index].equals("null")){
            node = new TreeNode(Integer.valueOf(nodes[index]));
            node.left = deserialize(data);
            node.right = deserialize(data);
        }
        return node;

    }
}