二叉树的锯齿形层序遍历 图解题解

这道题到底在问什么

输入

上图这棵 12 节点树

输出

[[3],[20,9],[8,10,15,7],[5,6,4,2,1]]

最优解：一步一步想明白

1. 3思路一句话：BFS 一点没变，只用一个 flag 控制——偶数层把该层结果 reverse。下面一步步演给你看。
2. 4根节点入队。第 1 层方向＝左到右。
3. 5出队 3：先按出队顺序攒进第 1 层缓冲。
4. 63 的孩子 9 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
5. 73 的孩子 20 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。 第 1 层（左→右）收完：[3]——队列里现在全是下一层，方向翻转，继续。
6. 8出队 9：先按出队顺序攒进第 2 层缓冲。
7. 99 的孩子 8 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
8. 109 的孩子 10 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
9. 11出队 20：先按出队顺序攒进第 2 层缓冲。
10. 1220 的孩子 15 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
11. 1320 的孩子 7 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。 第 2 层（右→左）：把出队序列 [9, 20] 翻转 → [20, 9]——队列里现在全是下一层，方向翻转，继续。
12. 14出队 8：先按出队顺序攒进第 3 层缓冲。
13. 158 的孩子 1 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
14. 168 的孩子 2 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
15. 17出队 10：先按出队顺序攒进第 3 层缓冲。
16. 1810 的孩子 4 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
17. 1910 的孩子 6 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
18. 20出队 15：先按出队顺序攒进第 3 层缓冲。
19. 2115 的孩子 5 入队（孩子永远按左右顺序入队，方向只影响“怎么收”）。
20. 22出队 7：先按出队顺序攒进第 3 层缓冲。 第 3 层（左→右）收完：[8, 10, 15, 7]——队列里现在全是下一层，方向翻转，继续。
21. 23出队 1：先按出队顺序攒进第 4 层缓冲。
22. 24出队 2：先按出队顺序攒进第 4 层缓冲。
23. 25出队 4：先按出队顺序攒进第 4 层缓冲。
24. 26出队 6：先按出队顺序攒进第 4 层缓冲。
25. 27出队 5：先按出队顺序攒进第 4 层缓冲。 第 4 层（右→左）：把出队序列 [1, 2, 4, 6, 5] 翻转 → [5, 6, 4, 2, 1]——队列里现在全是下一层，方向翻转，继续。

⚠️ 容易写错的地方

完整代码（Python / Java / C++）

def zigzagLevelOrder(root):
    if not root: return []
    res, q, leftToRight = [], deque([root]), True
    while q:
        level = []
        for _ in range(len(q)):       # 锁定本层个数
            node = q.popleft()        # 出队一个
            level.append(node.val)    # 永远按出队(左→右)攒
            if node.left:  q.append(node.left)   # 孩子照常左右入队
            if node.right: q.append(node.right)
        res.append(level if leftToRight else level[::-1])  # 偶数层翻转
        leftToRight = not leftToRight # 方向交替
    return res

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    boolean leftToRight = true;
    while (!q.isEmpty()) {
        int sz = q.size();                 // 锁定本层个数
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = 0; i < sz; i++) {
            TreeNode node = q.poll();      // 出队一个
            // 方向开关：左→右尾插，右→左头插，省去最后 reverse
            if (leftToRight) level.addLast(node.val);
            else             level.addFirst(node.val);
            if (node.left != null)  q.offer(node.left);   // 孩子照常左右入队
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
        leftToRight = !leftToRight;        // 方向交替
    }
    return res;
}

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    bool leftToRight = true;
    while (!q.empty()) {
        int sz = q.size();                 // 锁定本层个数
        vector<int> level(sz);
        for (int i = 0; i < sz; ++i) {
            TreeNode* node = q.front(); q.pop();  // 出队一个
            // 方向开关：决定值写进本层数组的哪一端
            int idx = leftToRight ? i : sz - 1 - i;
            level[idx] = node->val;
            if (node->left)  q.push(node->left);   // 孩子照常左右入队
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
        leftToRight = !leftToRight;        // 方向交替
    }
    return res;
}

复杂度

面试官可能追问