LeetCode 5 道簡單題專題 III：二叉樹之字形層序、有序數組/鏈表轉 BST、被圍繞區域、平衡二叉樹、最小深度

1. Binary Tree Zigzag Level Order Traversal

層序遍歷，奇數層左→右，偶數層右→左。用隊列 BFS，每層收集節點，按層號奇偶決定輸出順序。

vector> zigzagLevelOrder(TreeNode* root) {
    vector> res;
    if (!root) return res;
    queue q; q.push(root);
    bool l2r = true;
    while (!q.empty()) {
        int sz = q.size();
        vector level(sz);
        for (int i = 0; i < sz; ++i) {
            TreeNode* n = q.front(); q.pop();
            int idx = l2r ? i : sz - 1 - i;
            level[idx] = n->val;
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        res.push_back(level);
        l2r = !l2r;
    }
    return res;
}

2. Convert Sorted Array to BST

分治遞歸：中間元素作根，左半遞歸建左子樹，右半遞歸建右子樹。

TreeNode* sortedArrayToBST(vector& nums) {
    return build(nums, 0, nums.size()-1);
}
TreeNode* build(vector& nums, int l, int r) {
    if (l > r) return nullptr;
    int m = (l + r) >> 1;
    TreeNode* root = new TreeNode(nums[m]);
    root->left = build(nums, l, m-1);
    root->right = build(nums, m+1, r);
    return root;
}

3. Convert Sorted List to BST

快慢指針找中點，斷開鏈表，遞歸構建。或轉數組後同數組法。

TreeNode* sortedListToBST(ListNode* head) {
    return buildList(head, nullptr);
}
TreeNode* buildList(ListNode* l, ListNode* r) { // [l, r)
    if (l == r) return nullptr;
    ListNode *slow = l, *fast = l, *pre = nullptr;
    while (fast != r && fast->next != r) {
        pre = slow; slow = slow->next; fast = fast->next->next;
    }
    TreeNode* root = new TreeNode(slow->val);
    root->left = buildList(l, pre ? pre->next : slow);
    root->right = buildList(slow->next, r);
    return root;
}

4. Surrounded Regions (BFS 從邊界 'O' 擴散)

邊界 'O' 及其連通區域不可翻轉。BFS 標記所有不可翻轉點，最後掃描翻轉未標記的 'O'→'X'。

void solve(vector>& board) {
    int m = board.size(); if (!m) return;
    int n = board[0].size();
    vector> flag(m, vector(n));
    queue> q;
    // 入隊邊界 O
    for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j)
        if ((i==0||i==m-1||j==0||j==n-1) && board[i][j]=='O')
            q.emplace(i,j), flag[i][j]=1;
    // BFS
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    while (!q.empty()) {
        auto [x,y] = q.front(); q.pop();
        for (auto& d : dirs) {
            int nx=x+d[0], ny=y+d[1];
            if (nx>=0&&nx=0&&ny

5. Balanced Binary Tree
後序遞歸求深度，若任意節點左右深度差 ≥2 則不平衡。全局標記剪枝。
bool isBalanced(TreeNode* root) {
    bool ok = true;
    function dfs = [&](TreeNode* n) {
        if (!n || !ok) return 0;
        int l = dfs(n->left), r = dfs(n->right);
        if (abs(l-r) >= 2) ok = false;
        return max(l,r) + 1;
    };
    dfs(root);
    return ok;
}

6. Minimum Depth of Binary Tree
遞歸求最小深度。注意單子樹情況：若左/右為空，深度取另一邊+1，不可取 0。
int minDepth(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    int l = minDepth(root->left), r = minDepth(root->right);
    if (!l) return r + 1;
    if (!r) return l + 1;
    return min(l, r) + 1;
}

總結
五道二叉樹經典題：Zigzag BFS、分治構建 BST、鏈表快慢指針找中點、邊界 BFS 標記不可翻轉區域、後序剪枝判平衡、單子樹特判求最小深度。掌握這些模板，覆蓋二叉樹 80% 面試考點。