0589. N-ary Tree Preorder Traversal ================================== 题目信息 -------- :题号: 0589 :难度: Easy :主题: N 叉树、前序遍历、孩子顺序、值序列 :原题: `LeetCode 0589 `_ :重点: 先访问当前节点、再按 children 从左到右递归访问各子树、空树返回空数组 题目重述 -------- 给定一棵 N 叉树的根节点 ``root``,返回它的前序遍历节点值序列。 前序遍历先访问当前节点,再按照节点 ``children`` 数组中的既定顺序,从左到右遍历每棵子树。不能任意调整兄弟节点顺序;若树为空,返回空数组。 自建示例 -------- 节点拥有不同数量的孩子: .. code-block:: text 输入:根 1 的孩子为 [2,3,4],3 的孩子为 [5,6] 输出:[1,2,3,5,6,4] 解释:先访问根 1,再依次遍历 2 的子树、3 的子树和 4 的子树。 空树: .. code-block:: text 输入:root = null 输出:[] 解释:没有可访问节点。 栈模拟从左到右的前序顺序 ------------------------ 栈顶是下一次访问节点;弹出当前节点后,将其孩子从右到左压栈,最左孩子就会先出栈。节点值在压入子树之前记录,符合“根、左孩子、右孩子”的前序定义。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector preorder(Node* root) { if (root == nullptr) return {}; std::vector result; std::stack stack; stack.push(root); while (!stack.empty()) { Node* node = stack.top(); stack.pop(); result.push_back(node->val); for (auto it = node->children.rbegin(); it != node->children.rend(); ++it) { stack.push(*it); } } return result; } }; 代码分析 -------- 反向压入孩子使出栈顺序与原 children 顺序一致,每个节点只弹出一次。时间复杂度为 ``O(n)``,栈空间为 ``O(h)`` 到 ``O(n)``。