589. N-ary Tree Preorder Traversal

🟢   🔖  栈 树 深度优先搜索  🔗 LeetCode

题目

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, 104].
• 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. 二叉树的前序遍历
• 429. N 叉树的层序遍历
• 590. N 叉树的后序遍历

- [144. 二叉树的前序遍历](./0144.md)
- [429. N 叉树的层序遍历](https://leetcode.com/problems/n-ary-tree-level-order-traversal)
- [590. N 叉树的后序遍历](https://leetcode.com/problems/n-ary-tree-postorder-traversal)