题解 | #序列化二叉树#

基本思路

序列化时采用先序遍历，遇到空节点则记录为#，并且每个节点序列化后面都加个分隔符","，这样方便序列化的字符串能够定位每个节点，str是引用地址，虽然每一层都会有一个新的引用地址的值，但是操作的都是引用地址所指向的内存的值。

反序列化也采用先序遍历，先将字符串按分割符分割为节点数组，由数组下标记录当前创建的节点，再创建根节点记录数组的对应位置的元素，然后再递归创建左右子树，拼接到当前节点，要注意索引下标不能作为参数传入递归函数，这样每一层都会有一个新的索引下标，它是基本类型数据，传递的不是引用地址，所以还是用全局变量记录下标比较好。

还需要注意java的字符串是用equals方法比较，而不是用==。

参考

参考题解

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    // 采用先序遍历序列化树
    private void serializeFunction(TreeNode root, StringBuilder str) {
        if (root == null) {  // 空节点记录为#
            str.append("#").append(",");
            return;
        }

        str.append(root.val).append(","); // 非空节点要在后面加个分割符，方便反序列化时能够根据分割符分割节点数字
        // 然后再递归反序列化左右子树节点
        serializeFunction(root.left, str);
        serializeFunction(root.right, str);

        return;
    }
    private int index = 0;
    private TreeNode deserializeFuction(String[] nodeArray) {
        if (nodeArray[index].equals("#")) {  // java的字符串比较要用equals
            index++;
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(nodeArray[index++]));
        System.out.println(index);
        if (index == nodeArray.length) {
            return root;
        }
        else {
            root.left = deserializeFuction(nodeArray);
            root.right = deserializeFuction(nodeArray);
        }

        return root;
    }
    String Serialize(TreeNode root) {
        
        StringBuilder str = new StringBuilder();
        serializeFunction(root, str);

        return str.toString();
    }
    TreeNode Deserialize(String str) {
       String[] nodeArray = str.split(",");
       TreeNode root = deserializeFuction(nodeArray);
       return root;
    }
}