589. N 叉树的前序遍历
589. N 叉树的前序遍历
题目
Given the root
of an n-ary tree, return the preorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]
Constraints:
- The number of nodes in the tree is in the range
[0, 10^4]
. 0 <= Node.val <= 10^4
- The height of the n-ary tree is less than or equal to
1000
.
Follow up: Recursive solution is trivial, could you do it iteratively?
题目大意
给定一个 n
叉树的根节点 root
,返回 其节点值的 前序遍历 。
n
叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null
分隔(请参见示例)。
解题思路
思路一:递归
对于 n 叉树,node.children
表示节点的所有子节点。从根节点开始前序遍历,在访问每个节点时,将其值添加到结果数组中,然后递归地对每个子节点进行前序遍历。
思路二:迭代
也可以用迭代的方式实现思路一的递归函数,使用一个栈 stack
,初始化时将根节点入栈。在循环中,每次弹出栈顶节点,访问该节点,然后按逆序将其子节点入栈。这样保证了下一个要访问的节点是栈顶的子节点。
两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而迭代的时候需要显式地将这个栈模拟出来。
代码
/**
* @param {Node|null} root
* @return {number[]}
*/
var preorder = function (root) {
if (!root) return [];
let res = [root.val];
for (let i of root.children) {
res.push(...preorder(i));
}
return res;
};
/**
* @param {Node|null} root
* @return {number[]}
*/
var preorder = function (root) {
if (!root) return [];
let stack = [root];
let res = [];
while (stack.length) {
let node = stack.pop();
res.push(node.val);
for (let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i]);
}
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
144 | 二叉树的前序遍历 | [✓] | 栈 树 深度优先搜索 1+ | |
429 | N 叉树的层序遍历 | 树 广度优先搜索 | ||
590 | N 叉树的后序遍历 | [✓] | 栈 树 深度优先搜索 |