二叉树的锯齿形层次遍历（Zigzag Level Order Traversal）实现与解析

二叉树的锯齿形层次遍历（Zigzag Level Order Traversal）是一种特殊的层次遍历方式，它要求我们在遍历二叉树时，按照层次从左到右或从右到左交替进行。具体来说，第一层从左到右，第二层从右到左，第三层从左到右，以此类推。

实现思路

1. 使用队列进行层次遍历：我们可以使用队列来实现层次遍历。首先将根节点入队，然后逐层处理队列中的节点。

2. 使用标志位控制遍历方向：我们可以使用一个标志位（如 leftToRight）来控制当前层的遍历方向。当 leftToRight 为 true 时，从左到右遍历；当 leftToRight 为 false 时，从右到左遍历。

3. 使用双端队列（Deque）或数组反转：为了在从右到左遍历时能够高效地插入节点，我们可以使用双端队列（Deque）或者在遍历完一层后对结果进行反转。

代码实现

以下是使用 JavaScript 实现的锯齿形层次遍历代码：

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function zigzagLevelOrder(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];
    let leftToRight = true;

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();

            if (leftToRight) {
                currentLevel.push(node.val);
            } else {
                currentLevel.unshift(node.val);
            }

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(currentLevel);
        leftToRight = !leftToRight;
    }

    return result;
}

// 示例用法
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

console.log(zigzagLevelOrder(root));
// 输出: [[3], [20, 9], [15, 7]]

代码解释

1. TreeNode 类：定义了二叉树的节点结构，每个节点包含 val（节点值）、left（左子节点）和 right（右子节点）。

2. zigzagLevelOrder 函数：

   • 首先检查根节点是否为空，如果为空则返回空数组。
   • 使用队列 queue 来存储当前层的节点。
   • leftToRight 标志位用于控制当前层的遍历方向。
   • 在每一层的遍历中，根据 leftToRight 的值决定是将节点值添加到 currentLevel 的开头还是末尾。
   • 遍历完一层后，将 currentLevel 添加到 result 中，并反转 leftToRight 的值。
   • 最后返回 result。

复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树的节点数。每个节点都会被访问一次。
• 空间复杂度：O(M)，其中 M 是二叉树的最大宽度（即某一层的最大节点数）。在最坏情况下，队列中会存储一层的所有节点。

总结

锯齿形层次遍历是一种常见的二叉树遍历方式，通过使用队列和标志位，我们可以高效地实现这一遍历方式。在实际应用中，这种遍历方式可以用于解决一些特定的问题，如按层打印二叉树、计算每层的最大值等。