【题目描述】

ACWing 50. 序列化二叉树

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

    // Encodes a tree to a single string.

    int u = 0;
    String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs_s(root, sb);
        return sb.toString();
    }
    /**
     * 前序遍历方式序列化二叉树 每个节点值以空格隔开
     * 根左右
    */
    void dfs_s(TreeNode root, StringBuilder res){
        if( root == null ){
            res.append("null").append(' ');
            return;
        }
        res.append(root.val).append(' ');
        dfs_s(root.left, res);
        dfs_s(root.right, res);
    }
    /**
     *反序列化 
     */
    // Decodes your encoded data to tree.
    TreeNode deserialize(String data) {

        char c[] = data.toCharArray();
        TreeNode root = dfs_d(c);
        return root;
    }

    TreeNode dfs_d(char c[]){
        //u 是全局变量 
        if( u == c.length ) return null;
        int k = u;
        //寻找节点（有值节点和空节点）
        while( c[k] != ' ') k ++;
        //空节点
        if(c[u] == 'n'){
            u = k + 1;  //指向下一个节点
            return null;
        }
        //有值节点值为c[u : k)
        int val = 0, sign = 1;
        if( u < k && c[u] == '-'){
            sign = -1;
            u ++; //跳过 符号位
        }
        for(int i = u; i < k ; i ++) 
            val = val * 10 + (c[i] - '0');
        val *= sign;
        u = k + 1;
        //构建二叉树
        TreeNode root =  new TreeNode(val);
        root.left = dfs_d(c);
        root.right = dfs_d  (c);
        return root;
    }
}