之字打印二叉树C语言

之字打印（Zigzag Level Order Traversal）是一种遍历二叉树的方式，它按照从上到下、先左后右的顺序逐层打印节点，但每层的节点排列顺序不同，第一层从左到右，第二层从右到左，第三层又从左到右，以此类推。在C语言中，你可以通过队列数据结构来实现这种遍历。

以下是C语言中之字打印二叉树的一个基本步骤：

1. 定义一个结构体表示二叉树节点，并包含指向左右子节点的指针。
2. 初始化一个队列，用于存储当前层的所有节点。
3. 创建一个二维数组或动态内存来保存结果，因为队列可能会有奇数或偶数长度。
4. 遍历树：
- 初始化队列，将根节点入队。
- 当队列非空时：
a. 每次循环，先出队一层的节点，然后将它们的左右子节点分别入队。如果这是当前层的第一个节点，则按正常顺序添加；如果是交替方向，就倒序添加。
b. 更新二维数组，记录当前层的结果。
5. 返回结果数组。

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

void zigzagLevelOrder(TreeNode* root, int row, int* result) {
    if (root == NULL) return;
    if (row % 2 == 0) { // 奇数行，从左往右
        result[row] = root->val;
        zigzagLevelOrder(root->right, row + 1, result);
        zigzagLevelOrder(root->left, row + 1, result);
    } else { // 偶数行，从右往左
        result[row] = root->val;
        zigzagLevelOrder(root->left, row + 1, result);
        zigzagLevelOrder(root->right, row + 1, result);
    }
}

// 示例用法
int main() {
    TreeNode* root = ...; // 初始化二叉树
    int rows;
    int* result = malloc(sizeof(int) * rows); // 预计层数
    zigzagLevelOrder(root, 0, result);
    for (int i = 0; i < rows; i++) {
        printf("%d ", result[i]);
    }
    free(result);
    return 0;
}