code二叉树的序列化与反序列化

原题链接:
https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

法1 dfs

写法1 重构时使用cur进行标记 会快一些

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

    // Encodes a tree to a single string.
    /*
    *   前序遍历 序列化编译为字符串
    * */

    public String serialize(TreeNode root) {
        if (root == null){
            return "N";
        }
        
        return root.val + "," +  serialize(root.left) + "," + serialize(root.right);
    }

    // 在leetcode中 static变量只会初始化一次 
    // 之后每次会沿用上一次的值 如果只是作为记数值 那么每次都需要再调用前先初始化一下
    public static int cur = 0;
    // Decodes your encoded data to tree.
    // 用于反序列化
    public TreeNode dfs2(String[] split){
        // System.out.println(cur);
        // 为空则直接返回
        // 字符串不能用 "==" 进行比较 否则比较的是地址会出现问题
        if (cur >= split.length || split[cur].equals("N")){
            cur++;
            return null;
        }

        TreeNode node = new TreeNode(Integer.parseInt(split[cur]));
        cur++;

        node.left = dfs2(split);
        node.right = dfs2(split);

        return node;
    }


    public TreeNode deserialize(String data) {
        // 根据, 进行拆分
        cur = 0;
        String[] split = data.split(",");
        return dfs2(split);
    }
}

// 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));

写法2 直接使用list 会比较简洁一些 也不容易出错

法2 BFS

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

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null){
            return "null";
        }

        StringBuilder res = new StringBuilder();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            var  node = queue.poll();
            if (node == null){
                res.append("null,");
                continue;
            }

            res.append(node.val + ",");
            queue.offer(node.left);
            queue.offer(node.right);
        }

        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        
        for(var x : split){
            System.out.println(x);
        }
        
        if(split[0] == "null"){
            return null;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(split[0]));
        queue.offer(root);

        // 作为指针
        int cur = 1;
        int n = split.length;

        while (!queue.isEmpty()){
            var node = queue.poll();

            if (cur < n && !split[cur].equals("null")){
                node.left = new TreeNode(Integer.parseInt(split[cur]));
                queue.offer(node.left);
            }
            cur++;
            
            if(cur < n && !split[cur].equals("null")){
                node.right = new TreeNode(Integer.parseInt(split[cur]));
                queue.offer(node.right);
            }
            cur++;
        }
        
        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));