⭐ 题目日期：

字节 - 2024/11/26，字节 - 2024/9/18

🌳 题目描述：

示例 1：

🕵🏽 面试评估：

这道题考察二叉树的广度优先遍历(BFS)，要求候选人对层序遍历和 Z 字形顺序的核心逻辑有清晰的理解，能迅速提出双端队列作为实现的基础。难度中等偏上。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

这道题的关键是找到层与层之间的衔接规律。从根节点层很难发现，因为当前层只有一个节点，左右都可被打印。所以我们重点关注中间两层([1, 2], [3, 4, 5, 6])。

从 [2, 1] -> [3, 4, 5, 6]

在 [1, 2] 层，我们先从右边打印 2 (pollRight), 所以应该从左边加入子节点，而且是先加右子节点 6，因为要保持[3, 4, 5, 6] 或者 [6, 5, 4, 3] 的连续顺序。

从 [3, 4, 5, 6] -> [14, 13, 12, 11, 10, 9, 8, 7]

当 [1, 2] 层完成打印后，我们得到节点的顺序为，从左至右：[3, 4, 5, 6], 由于我们输出的顺序也应该为 [3, 4, 5, 6], 所以在 [3, 4, 5, 6] 层，我们应该从左边开始输出，将子节点从右边添加，同理为了维持连续的顺序，我们从右边先添加左节点，再添加右节点。得到 [7, 8, 9, 10, 11, 12, 13, 14], 然后到下一层又从右端打印，左端添加，以及保持连续的顺序，奇偶数层循环往复，直到遍历完二叉树中所有的节点。

💻代码：

Java

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<TreeNode> deque = new LinkedList<>();
        int level = 0;
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> curList = new ArrayList<>();
            while (size > 0) {
                if (level % 2 == 0) {
                    TreeNode curNode = deque.pollFirst();
                    curList.add(curNode.val);
                    if (curNode.left != null) {
                        deque.offerLast(curNode.left);
                    }
                    if (curNode.right != null) {
                        deque.offerLast(curNode.right);
                    }
                } else {
                    TreeNode curNode = deque.pollLast();
                    curList.add(curNode.val);
                    if (curNode.right != null) {
                        deque.offerFirst(curNode.right);
                    }
                    if (curNode.left != null) {
                        deque.offerFirst(curNode.left);
                    }
                }
                size--;
            }
            level++;
            result.add(new ArrayList<>(curList));
        }

        return result;
    }

Python

    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        if not root:
            return result

        deque_nodes = deque()
        level = 0
        deque_nodes.append(root)

        while deque_nodes:
            size = len(deque_nodes)
            cur_list = []
            for _ in range(size):
                if level % 2 == 0:
                    cur_node = deque_nodes.popleft()
                    cur_list.append(cur_node.val)
                    if cur_node.left:
                        deque_nodes.append(cur_node.left)
                    if cur_node.right:
                        deque_nodes.append(cur_node.right)
                else:
                    cur_node = deque_nodes.pop()
                    cur_list.append(cur_node.val)
                    if cur_node.right:
                        deque_nodes.appendleft(cur_node.right)
                    if cur_node.left:
                        deque_nodes.appendleft(cur_node.left)
            level += 1
            result.append(cur_list)

        return result

C++

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) {
            return result;
        }

        deque<TreeNode*> deque;
        int level = 0;
        deque.push_back(root);

        while (!deque.empty()) {
            int size = deque.size();
            vector<int> curList;

            while (size > 0) {
                if (level % 2 == 0) {
                    TreeNode* curNode = deque.front();
                    deque.pop_front();
                    curList.push_back(curNode->val);
                    if (curNode->left != nullptr) {
                        deque.push_back(curNode->left);
                    }
                    if (curNode->right != nullptr) {
                        deque.push_back(curNode->right);
                    }
                } else {
                    TreeNode* curNode = deque.back();
                    deque.pop_back();
                    curList.push_back(curNode->val);
                    if (curNode->right != nullptr) {
                        deque.push_front(curNode->right);
                    }
                    if (curNode->left != nullptr) {
                        deque.push_front(curNode->left);
                    }
                }
                size--;
            }

            level++;
            result.push_back(curList);
        }

        return result;
    }
};

🚵🏻复杂度分析：

时间复杂度：O(n), n 为二叉树中节点的个数

空间复杂度：O(n), O(n) 存储结果，如果不考虑结果的存储，额外空间主要用在临时存储当前层的节点，最坏情况当二叉树为满二叉树时，存储 n / 2 个节点，时间复杂度为 O(n)

🔬在线评测(Online Judge):

题目链接