題⽬描述

請實現兩個函數，分別⽤來序列化和反序列化⼆叉樹

⼆叉樹的序列化是指：把⼀棵⼆叉樹按照某種遍歷⽅式的結果以某種格式保存為字符串，從⽽使得內存中建⽴起來的⼆叉樹可以持久保存。序列化可以基於先序、中序、後序、層序的⼆叉樹遍歷⽅式來進⾏修改，序列化的結果是⼀個字符串，序列化時通過 某種符號表示空節點（ # ），以 ！ 表示⼀個結點值的結束（ value! ）。

⼆叉樹的反序列化是指：根據某種遍歷順序得到的序列化字符串結果str ，重構⼆叉樹。例如，我們可以把⼀個只有根節點為1的⼆叉樹序列化為" 1"，然後通過⾃⼰的函數來解析回這個⼆叉樹

示例1
輸⼊：{8,6,10,5,7,9,11}
返回值：{8,6,10,5,7,9,11}

思路及解答

前序遍歷（遞歸）

利用二叉樹的前序遍歷順序（根-左-右）進行序列化，並使用特殊字符（如"#"或"null"）表示空節點，以確保樹結構的唯一性。

序列化思路：從根節點開始，先輸出當前節點的值，然後遞歸地序列化左子樹和右子樹。遇到空節點時，輸出空標記（如"#"）。

反序列化思路：按照前序遍歷的順序，依次從序列化字符串中讀取節點值。如果讀取到空標記，則返回null；否則，用當前值創建節點，並遞歸構建其左子樹和右子樹

public class CodecPreOrder {

    // 序列化：將二叉樹轉換為字符串
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        // 刪除末尾多餘的分隔符（如果有）
        if (sb.length() > 0) {
            sb.setLength(sb.length() - 1);
        }
        return sb.toString();
    }

    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#").append(","); // 使用"#"表示空節點
            return;
        }
        sb.append(node.val).append(","); // 先處理根節點
        buildString(node.left, sb);     // 再遞歸處理左子樹
        buildString(node.right, sb);    // 最後遞歸處理右子樹
    }

    // 反序列化：將字符串還原為二叉樹
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) return null;
        // 將字符串按分隔符分割成列表
        LinkedList<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
        return buildTree(nodes);
    }

    private TreeNode buildTree(LinkedList<String> nodes) {
        if (nodes.isEmpty()) return null;
        String val = nodes.removeFirst(); // 按前序順序取出節點值
        if (val.equals("#")) return null; // 遇到空標記則返回null
        
        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = buildTree(nodes);  // 遞歸構建左子樹
        root.right = buildTree(nodes); // 遞歸構建右子樹
        return root;
    }
}

• 時間複雜度：O(n)，每個節點恰好被訪問一次。
• 空間複雜度：O(n)，遞歸調用棧的深度在最壞情況下（樹退化為鏈表）為O(n)，序列化字符串長度也與節點數n成線性關係。

層序遍歷（迭代）

層序遍歷（廣度優先搜索）更直觀，可以按層級順序處理節點，適合處理接近完全二叉樹的情況。

序列化思路：使用隊列輔助進行層序遍歷。從根節點開始，將節點值加入字符串，並將其非空子節點（即使是空節點也記錄）加入隊列，以確保樹結構信息完整。

反序列化思路：同樣使用隊列，根據序列化字符串的順序，依次為每個非空節點創建其左右子節點

public class CodecLevelOrder {

    // 序列化：層序遍歷二叉樹
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("#,"); // 空節點標記
                continue;
            }
            sb.append(node.val).append(",");
            // 即使子節點為空也加入隊列，以保留結構信息
            queue.offer(node.left);
            queue.offer(node.right);
        }
        // 移除末尾多餘的分隔符
        sb.setLength(sb.length() - 1);
        return sb.toString();
    }

    // 反序列化：根據層序序列重建樹
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) return null;
        String[] values = data.split(",");
        if (values[0].equals("#")) return null;
        
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int index = 1; // 指向當前待處理子節點的數組位置
        
        while (!queue.isEmpty() && index < values.length) {
            TreeNode parent = queue.poll();
            // 構建左子節點
            if (index < values.length && !values[index].equals("#")) {
                parent.left = new TreeNode(Integer.parseInt(values[index]));
                queue.offer(parent.left);
            }
            index++;
            // 構建右子節點
            if (index < values.length && !values[index].equals("#")) {
                parent.right = new TreeNode(Integer.parseInt(values[index]));
                queue.offer(parent.right);
            }
            index++;
        }
        return root;
    }
}

• 時間複雜度：O(n)，每個節點入隊、出隊各一次。
• 空間複雜度：O(n)，隊列中最多同時存儲約n/2個節點（完全二叉樹的最後一層）。

二叉搜索樹（BST）前序優化

對於二叉搜索樹（BST），可以利用其中序遍歷為升序的特性，僅通過前序或後序序列即可唯一確定樹結構，無需顯式存儲空節點。

序列化思路：對BST進行前序遍歷，將節點值拼接成字符串。由於BST的性質，中序遍歷就是節點值的升序排列，因此僅憑前序遍歷結果就能唯一確定樹結構。

反序列化思路：根據前序遍歷結果，第一個元素為根節點。剩餘元素中，所有小於根節點的值構成左子樹的前序遍歷，大於根節點的值構成右子樹的前序遍歷。遞歸進行即可重建BST

public class CodecBST {

    // 序列化：對BST進行前序遍歷
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        preorderTraversal(root, sb);
        return sb.substring(0, sb.length() - 1); // 去掉末尾分隔符
    }

    private void preorderTraversal(TreeNode node, StringBuilder sb) {
        if (node == null) return;
        sb.append(node.val).append(" "); // 用空格分隔，注意BST序列化可不顯式標記空節點
        preorderTraversal(node.left, sb);
        preorderTraversal(node.right, sb);
    }

    // 反序列化：利用BST性質重建樹
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        // 將字符串轉換為整數列表
        int[] values = Arrays.stream(data.split(" ")).mapToInt(Integer::parseInt).toArray();
        return buildBST(values, 0, values.length - 1);
    }

    private TreeNode buildBST(int[] preorder, int start, int end) {
        if (start > end) return null;
        TreeNode root = new TreeNode(preorder[start]);
        // 找到右子樹的開始索引（第一個大於根節點值的元素）
        int rightStart = start + 1;
        while (rightStart <= end && preorder[rightStart] < preorder[start]) {
            rightStart++;
        }
        // 遞歸構建左子樹和右子樹
        root.left = buildBST(preorder, start + 1, rightStart - 1);
        root.right = buildBST(preorder, rightStart, end);
        return root;
    }
}

• 時間複雜度：O(n log n) 最壞情況下（BST退化為鏈表）為O(n²)，平均情況下為O(n log n)。這是因為在重建過程中，需要為每個節點在序列中查找其左右子樹的分界點。
• 空間複雜度：O(n)，用於存儲遞歸棧和序列化字符串。