590. N 叉树的后序遍历

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

题目

Given the root of an n-ary tree, return the postorder 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: [5,6,3,2,4,1]

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: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

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 叉树，node.children 表示节点的所有子节点。从根节点开始遍历，在访问每个节点时，递归地对每个子节点进行后序遍历，然后将其值添加到结果数组中。

---

思路二：迭代

同样，通过使用栈来模拟递归的过程，可以迭代地完成后序遍历。

先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后再反转 res 数组，输出的结果顺序就是左右中了。

具体实现时，将当前节点的值插入结果数组时，可以使用 unshift 方法。

代码

递归

/**
 * @param {Node|null} root
 * @return {number[]}
 */
var postorder = function (root) {
	if (!root) return [];
	let res = [];
	for (let i of root.children) {
		res.push(...postorder(i));
	}
	res.push(root.val);
	return res;
};

迭代

/**
 * @param {Node|null} root
 * @return {number[]}
 */
var postorder = function (root) {
	if (!root) return [];
	let stack = [root];
	let res = [];
	while (stack.length) {
		let node = stack.pop();
		res.unshift(node.val);
		for (let i of node.children) {
			stack.push(i);
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
145	二叉树的后序遍历	[✓]	栈 树 深度优先搜索 1+
429	N 叉树的层序遍历		树 广度优先搜索
589	N 叉树的前序遍历	[✓]	栈 树 深度优先搜索