1、解题思路

之字形层序遍历可以通过层序遍历的变种来实现：

  1. 仍然使用队列进行层序遍历。
  2. 根据当前层数的奇偶性决定遍历方向： 奇数层（如第1层）从左到右遍历。偶数层（如第2层）从右到左遍历。
  3. 可以通过反转当前层的列表或使用双端队列来控制遍历方向。

2、代码实现

C++
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <thread>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > Print(TreeNode* pRoot) {
        // write code here
        vector<vector<int>> result;
        if (pRoot == nullptr) {
            return result;
        }

        queue<TreeNode*> q;
        q.push(pRoot);
        bool leftToRight = true;    // 控制遍历方向

        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> curLevel(levelSize);

            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();

                // 根据方向决定插入位置
                int index = leftToRight ? i : levelSize - 1 - i;
                curLevel[index] = node->val;

                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }

            result.push_back(curLevel);
            leftToRight = !leftToRight; // 切换方向
        }

        return result;
    }
};
Python
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return int整型二维数组
#

from typing import List, Optional
from collections import deque

class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        # write code here
        result = []
        if not pRoot:
            return result
        
        queue = deque([pRoot])
        left_to_right = True  # 控制遍历方向
        
        while queue:
            level_size = len(queue)
            current_level = deque()
            
            for _ in range(level_size):
                node = queue.popleft()
                
                # 根据方向决定插入位置
                if left_to_right:
                    current_level.append(node.val)
                else:
                    current_level.appendleft(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(list(current_level))
            left_to_right = not left_to_right  # 切换方向
        
        return result

3、复杂度分析

  • 时间复杂度：O(n)，每个节点被访问一次。
  • 空间复杂度：O(n)，队列中最多存储 n 个节点。