Medium

题目描述

给你二叉树的根节点 root，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

解题思路

这道题是在二叉树层序遍历的基础上加了锯齿形的要求，核心思路有两种：

方法一：BFS + 反转 使用标准的层序遍历（BFS），对于每一层的节点，奇数层正常添加，偶数层需要反转顺序。可以用一个布尔变量 leftToRight 来标记当前层的遍历方向，每遍历完一层就切换方向。

方法二：双端队列 使用双端队列（deque）来控制节点的添加顺序。奇数层从左到右添加到队列尾部，偶数层从右到左添加到队列头部，这样可以直接得到锯齿形的结果。

推荐方法一，因为它更直观易懂，代码逻辑清晰。我们使用队列进行标准BFS遍历，记录每一层的节点数量，然后根据层数的奇偶性决定是否需要反转当前层的结果。

时间复杂度为 O(n)，其中 n 是树中节点的数量，每个节点都会被访问一次。空间复杂度为 O(w)，其中 w 是树的最大宽度。

代码实现

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        
        vector<vector<int>> result;
        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;
        
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            if (!leftToRight) {
                reverse(level.begin(), level.end());
            }
            
            result.push_back(level);
            leftToRight = !leftToRight;
        }
        
        return result;
    }
};

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        result = []
        queue = collections.deque([root])
        left_to_right = True
        
        while queue:
            size = len(queue)
            level = []
            
            for _ in range(size):
                node = queue.popleft()
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            if not left_to_right:
                level.reverse()
            
            result.append(level)
            left_to_right = not left_to_right
        
        return result

public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        if (root == null) return new List<IList<int>>();
        
        var result = new List<IList<int>>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        bool leftToRight = true;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            var level = new List<int>();
            
            for (int i = 0; i < size; i++) {
                var node = queue.Dequeue();
                level.Add(node.val);
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            if (!leftToRight) {
                level.Reverse();
            }
            
            result.Add(level);
            leftToRight = !leftToRight;
        }
        
        return result;
    }
}

var zigzagLevelOrder = function(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    let leftToRight = true;
    
    while (queue.length > 0) {
        const size = queue.length;
        const level = [];
        
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            level.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        if (!leftToRight) {
            level.reverse();
        }
        
        result.push(level);
        leftToRight = !leftToRight;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)n 为树中节点数量，每个节点访问一次
空间复杂度O(w)w 为树的最大宽度，队列最多存储一层的节点

相关题目