/**
 * @Projectname: LeetCode
 * @Filename: Codec
 * @Author: 杨逸
 * @Data:2023/8/21 19:27
 * @Description: 二叉树的序列化与反序列化
 */


import java.util.HashMap;
import java.util.Map;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private static StringBuilder data = new StringBuilder("");
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        data.delete(0,data.length());
        encode(root,0,true);
        return data.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data1) {
        return decode(data1);
    }


    private void encode(TreeNode root,int h,boolean isLeft){
        if (root == null){
            return;
        }
        for (int i = 0; i < h; i++) {
            //使用 "-" 表示当前节点的高度
            data.append(".");
        }
        data.append(root.val);
        if (!isLeft){
            //在右子节点后加 "!" 表示为右节点
            data.append("!");
        }
        //递归
        encode(root.left,h+1,true);
        encode(root.right,h+1,false);
    }

    private TreeNode decode(String data1){
        if (data1.equals("")){
            return null;
        }
        char[] chars = data1.toCharArray();
        Map<Integer,TreeNode> map = new HashMap<>();
        int index = 0;
        StringBuilder value = new StringBuilder();
        //拼接根节点的值
        while(index < data1.length() && chars[index] != '.'){
            value.append(chars[index++]);
        }
        //构建根节点
        TreeNode root = new TreeNode(Integer.valueOf(value.toString()));
        map.put(0,root);
        int count = 0;
        while(index < chars.length){
            count = 0;
            //获取节点的高度
            while(index < data1.length() && chars[index] == '.'){
                count++;
                index++;
            }
            //获取节点的值
            value.delete(0,value.length());
            while(index < data1.length() && chars[index] != '.' && chars[index] != '!'){
                value.append(chars[index++]);
            }
            //构建节点
            TreeNode node = new TreeNode(Integer.valueOf(value.toString()));
            //获取当前节点的父节点
            TreeNode cur_root = map.get(count - 1);
            //挂载当前节点,根据后一个字符是否为 "!"进行挂载
            if (index < data1.length() && chars[index] == '!'){
                //右子节点
                cur_root.right = node;
                index++;
            }else{
                //左子节点
                cur_root.left = node;
            }

            //将当前节点加入哈希表中
            map.put(count,node);
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));