0589. N-ary Tree Preorder Traversal¶
题目信息¶
- 题号:
0589
- 难度:
Easy
- 主题:
N 叉树、前序遍历、孩子顺序、值序列
- 原题:
- 重点:
先访问当前节点、再按 children 从左到右递归访问各子树、空树返回空数组
题目重述¶
给定一棵 N 叉树的根节点 root,返回它的前序遍历节点值序列。
前序遍历先访问当前节点,再按照节点 children 数组中的既定顺序,从左到右遍历每棵子树。不能任意调整兄弟节点顺序;若树为空,返回空数组。
自建示例¶
节点拥有不同数量的孩子:
输入:根 1 的孩子为 [2,3,4],3 的孩子为 [5,6]
输出:[1,2,3,5,6,4]
解释:先访问根 1,再依次遍历 2 的子树、3 的子树和 4 的子树。
空树:
输入:root = null
输出:[]
解释:没有可访问节点。
栈模拟从左到右的前序顺序¶
栈顶是下一次访问节点;弹出当前节点后,将其孩子从右到左压栈,最左孩子就会先出栈。节点值在压入子树之前记录,符合“根、左孩子、右孩子”的前序定义。
C++ 实现¶
class Solution {
public:
std::vector<int> preorder(Node* root) {
if (root == nullptr) return {};
std::vector<int> result;
std::stack<Node*> 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)。