题解 | #序列化二叉树#

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 {
    String Serialize(TreeNode root) {
        // 处理树为空的情况
        if (root == null) {
            return "null";
        }

        // 分别对树进行先序遍历和中序遍历，结果放在stringbuilder中，以","分割
        StringBuilder preorderSb = new StringBuilder();
        StringBuilder inoderSb = new StringBuilder();
        preorder(preorderSb, root);
        inorder(inoderSb, root);
        
        // 删除最后一个","
        preorderSb.deleteCharAt(preorderSb.length() - 1);
        inoderSb.deleteCharAt(inoderSb.length() - 1);

        // 两个结果以":"相连
        return preorderSb.append(":").append(inoderSb).toString();
    }

    TreeNode Deserialize(String str) {
        // 树为空
        if ("null".equals(str)) {
            return null;
        }

        // 取出先序和中序遍历结果
        String[] strs = str.split(":");
        String preorderStr = strs[0];
        String inorderStr = strs[1];
        String[] preorderRes = preorderStr.split(",");
        String[] inorderRes = inorderStr.split(",");

        // 根据先序遍历和中序遍历重建二叉树
        return buildTree(preorderRes, inorderRes, 0, inorderRes.length - 1, 0,
                         preorderRes.length - 1);
    }

    TreeNode buildTree(String[] preoders, String[] inorders, int inLeft,
                       int inRight, int preStart, int preEnd) {
        if (preStart > preEnd) {
            return null;
        }
        
        // 先序遍历的第一个节点即为根节点
        String current = preoders[preStart];
        TreeNode root = new TreeNode(Integer.parseInt(current));
        
        // 在中序遍历中找到根节点的左节点数量，可以用map优化时间复杂度
        int leftCnt = 0;
        for (int i = inLeft; i <= inRight; i++) {
            if (current.equals(inorders[i])) {
                break;
            }
            leftCnt++;
        }

        // 递归地重建左右子树
        root.left = buildTree(preoders, inorders, inLeft, inLeft + leftCnt - 1,
                              preStart + 1, preStart + leftCnt);
        root.right = buildTree(preoders, inorders, inLeft + leftCnt + 1, inRight,
                               preStart + leftCnt + 1, preEnd);
        return root;
    }

    private void preorder(StringBuilder sb, TreeNode root) {
        if (root == null) {
            return;
        }
        sb.append(root.val);
        sb.append(",");
        preorder(sb, root.left);
        preorder(sb, root.right);
    }

    private void inorder(StringBuilder sb, TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(sb, root.left);
        sb.append(root.val);
        sb.append(",");
        inorder(sb, root.right);
    }
}