590. N-ary Tree Postorder Traversal
590. N-ary Tree Postorder Traversal
题目
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:
![](https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png)
Input: root = [1,null,3,2,4,null,5,6]
Output: [5,6,3,2,4,1]
Example 2:
![](https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png)
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, 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 叉树,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. 二叉树的后序遍历](./0145.md)
- [429. N 叉树的层序遍历](https://leetcode.com/problems/n-ary-tree-level-order-traversal)
- [589. N 叉树的前序遍历](https://leetcode.com/problems/n-ary-tree-preorder-traversal)