医院网站模板_重庆网站优化软件_优质外链平台_广告营销包括哪些方面

力扣题目：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;
}

五、复杂度分析

1. 时间复杂度

无论是递归还是迭代方法，每个节点都恰好被访问一次，因此时间复杂度均为 $O(n)$ ，其中 $n$ 是树中节点的数量。

2. 空间复杂度

递归方法：递归调用栈的深度取决于树的高度。在最坏情况下，树退化为一条链，递归栈的深度为 $n$ ，空间复杂度为 $O(n)$ ；平均情况下，空间复杂度为 $O(log(n))$ 。
迭代方法：在最坏情况下，栈需要存储树的所有节点，空间复杂度为 $O(n)$ 。

六、总结

通过递归和迭代两种方法，我们成功实现了 N 叉树的前序遍历。递归方法代码简洁直观，适合理解和实现；迭代方法则避免了递归调用栈的开销，在某些场景下可能更具优势。在实际应用中，可以根据具体需求选择合适的方法。希望本文能帮助你更好地理解 N 叉树的前序遍历以及 C 语言的实现。