N叉树的前序遍历实现（递归与迭代）

"N叉树的前序遍历（递归+迭代）1" 在计算机科学中，树是一种数据结构，而N叉树是其中的一种特殊类型，它的每个节点可以有N个子节点，N可以是任意正整数。前序遍历是遍历树的一种方法，通常用于访问树的节点，其顺序是：先访问根节点，然后遍历左子树，最后遍历右子树。在N叉树的情况下，这个顺序稍有不同，但基本思想保持不变：先访问根节点，然后遍历所有子节点，按照某种顺序。 对于给定的问题，我们需要实现N叉树的前序遍历。有两种常见的方法来实现这一点：递归和迭代。 递归方法： 递归是最直观的方法，通常也是最容易理解的。在C++的代码中，我们可以定义一个`Node`类来表示树的节点，包含一个整数值`val`和一个`children`向量，存储子节点的指针。然后，我们创建一个`Solution`类，包含一个名为`travel`的成员函数，该函数接受一个节点和一个结果向量`res`作为参数。如果节点为空，函数返回；否则，将当前节点的值添加到结果向量，然后对每个子节点递归调用`travel`函数。最后，`preorder`函数接收树的根节点，并初始化结果向量，然后调用`travel`函数开始遍历。 迭代方法： 迭代方法使用栈来模拟递归过程，这种方法通常在处理大规模数据或者避免递归深度过深时更受欢迎。在C++的代码中，迭代的`preorder`函数同样在`Solution`类中，它初始化一个空的结果向量和一个栈，然后将根节点压入栈中。当栈非空时，循环执行以下步骤：弹出栈顶的节点u，将其值添加到结果向量，然后将u的所有子节点（从后往前，即逆序）压入栈中。这样做保证了子节点会在父节点之后被处理，符合前序遍历的顺序。 以下是完整的迭代版本的`preorder`函数： ```cpp vector<int> preorder(Node* root) { vector<int> res; stack<Node*> s; if (root != nullptr) { s.push(root); } while (!s.empty()) { Node* u = s.top(); s.pop(); res.push_back(u->val); for (int i = u->children.size() - 1; i >= 0; i--) { s.push(u->children[i]); } } return res; } ``` 在这两种方法中，递归方法易于理解和实现，但可能面临栈溢出问题，特别是对于深度很大的树。而迭代方法虽然实现起来相对复杂，但它可以处理任意大小的树，且不需要担心栈溢出。在实际应用中，根据场景和性能需求，可以选择合适的方法进行实现。