LeetCode 297. 二叉樹序列化與反序列化：層序遍歷 + 索引映射完整解法

題目要求

設計算法將二叉樹序列化為字符串，並能從字符串反序列化重建原樹。格式不限，但需無狀態（不使用類成員/全局/靜態變量存狀態）。

採用 LeetCode 官方格式：層序遍歷，null 表示空節點，如 [1,2,3,null,null,4,5]。

序列化：標準層序遍歷（BFS）

反序列化核心難點：父子索引映射
若為完全二叉樹，父索引 i 對應子索引 2i+1, 2i+2。但層序含 null 時，實際索引需扣除前序 null 數：
數組: [5, 4, 7, 3, null, 2, null, -1, null, 9, ...]
索引:  0  1  2  3   4   5   6   7   8   9
節點 2 在索引 5，其左子 9 在索引 9（而非 2*5+1=11）
原因：索引 4 是 null，佔位但無子節點，導致後續索引前移 2 位

規律：節點 i 的左右子索引 = 2*(i - nullCount[i]) + 1 和 +2，其中 nullCount[i] 為 i 前的 null 總數。

Java 完整反序列化實現
 0) nullCnt[i] = nullCnt[i-1];
        if ("null".equals(vals[i])) {
            nodes[i] = null;
            nullCnt[i]++;
        } else {
            nodes[i] = new TreeNode(Integer.parseInt(vals[i]));
        }
    }

    for (int i = 0; i < n; ++i) {
        if (nodes[i] == null) continue;
        int leftIdx = 2 * (i - nullCnt[i]) + 1;
        int rightIdx = leftIdx + 1;
        if (leftIdx < n) nodes[i].left = nodes[leftIdx];
        if (rightIdx < n) nodes[i].right = nodes[rightIdx];
    }
    return nodes[0];
}


複雜度分析

  
時間：O(n)，兩次線性掃描。
  
空間：O(n)，存儲節點數組與前綴和。


關鍵優勢

  
無遞歸、無棧、無狀態，完全滿足題目約束。
  
索引映射邏輯通用，可擴展到其他層序序列化格式。