当前位置：首页 > article >正文

LeetCode 589

article 2025/2/27 6:15:01

力扣题目：N 叉树的前序遍历

一、题目背景与描述

在算法和数据结构的领域中，树的遍历是一个基础且重要的操作。今天我们要探讨的是 N 叉树的前序遍历问题。N 叉树是一种树形数据结构，每个节点可以有零个或多个子节点。

题目要求是给定一个 N 叉树的根节点 root，返回其节点值的前序遍历结果。这里的 N 叉树在输入时按层序遍历进行序列化表示，每组子节点由空值分隔。

它的序列化表示为 [1,null,3,2,4,null,5,6]。我们的目标就是将这个树以根节点 -> 子树 1 -> 子树 2 -> ... -> 子树 N 的顺序遍历，并输出节点值序列。

二、前序遍历的概念

前序遍历是树的一种深度优先遍历方式，对于 N 叉树而言，其遍历顺序为：

访问根节点。
递归地对根节点的每一个子节点进行前序遍历。

以刚才的 3 叉树为例，前序遍历的结果应该是 [1, 3, 5, 6, 2, 4]。

三、解题思路

前序遍历的顺序是：根节点 -> 左子树 -> 右子树（对于 n 叉树来说就是根节点 -> 第一棵子树 -> 第二棵子树 -> … -> 第 n 棵子树）。

我们可以使用递归和迭代两种方法来解决这个问题。

递归方法：
- 访问根节点，并将根节点的值加入结果列表。
- 递归地对根节点的每一棵子树进行前序遍历。
迭代方法：
- 使用栈来模拟递归过程。
- 首先将根节点入栈。
- 当栈不为空时，弹出栈顶元素，将其值加入结果列表，并将其所有子节点逆序入栈（因为栈是后进先出，逆序入栈才能保证正确的遍历顺序）。

四、C 语言代码实现

1. 节点结构定义

首先，我们需要定义 N 叉树的节点结构。在 C 语言中，可以使用结构体来实现：

typedef struct Node {
    int val;
    int numChildren;
    struct Node** children;
} Node;

这里，val 表示节点的值，numChildren 表示该节点的子节点数量，children 是一个指向子节点指针数组的指针。

2. 创建节点函数

为了方便构建 N 叉树，我们编写一个创建节点的函数：

Node* createNode(int val, int numChildren) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->numChildren = numChildren;
    node->children = (Node**)malloc(numChildren * sizeof(Node*));
    return node;
}

该函数接受节点的值和子节点数量作为参数，动态分配内存并初始化节点。

3. 递归实现前序遍历

递归是实现前序遍历的一种直观方法。以下是具体代码：

// 递归方法实现前序遍历
void preorderRecursive(Node* root, int* result, int* index) {
    if (root == NULL) return;
    result[(*index)++] = root->val;
    for (int i = 0; i < root->numChildren; i++) {
        preorderRecursive(root->children[i], result, index);
    }
}

// 计算树中节点的数量
int countNodes(Node* root) {
    if (root == NULL) return 0;
    int count = 1;
    for (int i = 0; i < root->numChildren; i++) {
        count += countNodes(root->children[i]);
    }
    return count;
}

// 递归方法调用函数
int* preorder_recursive(Node* root, int* returnSize) {
    *returnSize = countNodes(root);
    int* result = (int*)malloc(*returnSize * sizeof(int));
    int index = 0;
    preorderRecursive(root, result, &index);
    return result;
}

preorderRecursive 函数是核心的递归函数，它先访问根节点，然后递归地遍历每个子节点。
countNodes 函数用于计算树中节点的总数，以便为结果数组分配合适的内存。
preorder_recursive 函数是对外的调用接口，它负责分配结果数组，并调用 preorderRecursive 函数完成遍历。

4. 迭代实现前序遍历

除了递归，我们还可以使用迭代的方法，借助栈来模拟递归过程：

// 迭代方法实现前序遍历
int* preorder_iterative(Node* root, int* returnSize) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    // 计算节点数量
    *returnSize = countNodes(root);
    int* result = (int*)malloc(*returnSize * sizeof(int));
    int index = 0;

    // 栈的最大容量假设为节点数量
    Node** stack = (Node**)malloc(*returnSize * sizeof(Node*));
    int top = -1;
    stack[++top] = root;

    while (top >= 0) {
        Node* node = stack[top--];
        result[index++] = node->val;
        for (int i = node->numChildren - 1; i >= 0; i--) {
            stack[++top] = node->children[i];
        }
    }
    free(stack);
    return result;
}

首先，我们将根节点压入栈中。
当栈不为空时，弹出栈顶节点，将其值存入结果数组，并将其所有子节点逆序压入栈中。
重复上述步骤，直到栈为空。

5. 释放树的内存

为了避免内存泄漏，我们需要编写一个释放树内存的函数：

// 释放 N 叉树的内存
void freeTree(Node* root) {
    if (root == NULL) return;
    for (int i = 0; i < root->numChildren; i++) {
        freeTree(root->children[i]);
    }
    free(root->children);
    free(root);
}

6. 主函数测试

以下是一个简单的主函数，用于测试上述代码：

int main() {
    // 构建示例 N 叉树
    Node* root = createNode(1, 3);
    root->children[0] = createNode(3, 2);
    root->children[1] = createNode(2, 0);
    root->children[2] = createNode(4, 0);
    root->children[0]->children[0] = createNode(5, 0);
    root->children[0]->children[1] = createNode(6, 0);

    int returnSize;
    // 递归方法测试
    int* result_recursive = preorder_recursive(root, &returnSize);
    printf("递归方法前序遍历结果: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result_recursive[i]);
    }
    printf("\n");
    free(result_recursive);

    // 迭代方法测试
    int* result_iterative = preorder_iterative(root, &returnSize);
    printf("迭代方法前序遍历结果: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result_iterative[i]);
    }
    printf("\n");
    free(result_iterative);

    // 释放树的内存
    freeTree(root);

    return 0;
}