题目描述

给定一个二叉树，请实现一个函数，按照锯齿形（之字形）的顺序进行层序遍历。即第一层从左到右，第二层从右到左，第三层再从左到右，以此类推，返回遍历的结果。

示例：

给定二叉树:

    3
   / \
  9  20
    /  \
   15   7

按照锯齿形层序遍历的结果为：

[
  [3],
  [20, 9],
  [15, 7]
]

PHP 示例代码

<?php

class TreeNode {
    public $val;
    public $left;
    public $right;
    
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function zigzagLevelOrder($root) {
    if ($root === null) {
        return [];
    }
    
    $result = [];
    $queue = new SplQueue();
    $queue->enqueue([$root, 0]); // 节点和层级，层级用于判断方向
    $level = 0;
    
    while (!$queue->isEmpty()) {
        [$node, $currentLevel] = $queue->dequeue();
        
        if (!isset($result[$currentLevel])) {
            $result[$currentLevel] = [];
        }
        
        // 根据层级决定是添加到数组开头还是末尾
        if ($currentLevel % 2 === 0) {
            array_push($result[$currentLevel], $node->val);
        } else {
            array_unshift($result[$currentLevel], $node->val);
        }
        
        if ($node->left !== null) {
            $queue->enqueue([$node->left, $currentLevel + 1]);
        }
        if ($node->right !== null) {
            $queue->enqueue([$node->right, $currentLevel + 1]);
        }
    }
    
    // 移除空数组（如果树的高度是奇数，则最后一层可能为空）
    return array_values(array_filter($result));
}

// 示例用法
$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);

$result = zigzagLevelOrder($root);
print_r($result);
?>

Python 示例代码

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzagLevelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([(root, 0)])  # 节点和层级
    
    while queue:
        node, level = queue.popleft()
        
        if len(result) <= level:
            result.append([])
        
        # 根据层级决定是添加到列表开头还是末尾
        if level % 2 == 0:
            result[level].append(node.val)
        else:
            result[level].insert(0, node.val)
        
        if node.left:
            queue.append((node.left, level + 1))
        if node.right:
            queue.append((node.right, level + 1))
    
    return result

# 示例用法
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

result = zigzagLevelOrder(root)
print(result)

JavaScript 示例代码

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

function zigzagLevelOrder(root) {
    if (!root) return [];
    
    let result = [];
    let queue = [[root, 0]]; // 节点和层级
    
    while (queue.length > 0) {
        let [node, level] = queue.shift();
        
        if (!result[level]) {
            result[level] = [];
        }
        
        // 根据层级决定是添加到数组开头还是末尾
        if (level % 2 === 0) {
            result[level].push(node.val);
        } else {
            result[level].unshift(node.val);
        }
        
        if (node.left) {
            queue.push([node.left, level + 1]);
        }
        if (node.right) {
            queue.push([node.right, level + 1]);
        }
    }
    
    // 移除空数组
    return result.filter(arr => arr.length > 0);
}

// 示例用法
let 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);

let result = zigzagLevelOrder(root);
console.log(result);

以上代码均实现了二叉树的锯齿形层序遍历，并给出了示例用法。