590. N叉树的后序遍历

[buuing]

给定一个 N 叉树，返回其节点值的后序遍历。

例如，给定一个 3叉树 :

返回其后序遍历: [5,6,3,2,4,1].

说明: 递归法很简单，你可以使用迭代法完成此题吗?

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

我们通过两条分割线, 来寻找规律:

ACEDB | HIG | F
  左     右   父

这样来看, 我们只需要按照顺序父 -> 右 -> 左的顺序进行unshift操作即可

• 无脑递归

const postorder = root => {
  if (!root) return []
  const res = [root.val], children = root.children
  for (let i = children.length - 1; i >= 0; i--) {
    let child = children[i]
    res.unshift(...postorder(child))
  }
  return res
}

• 迭代 = 栈 + 深度优先搜索

const postorder = root => {
  if (!root) return []
  const res = [], stack = [root]
  while (stack.length) {
    let curr = stack.pop()
    res.unshift(curr.val)
    if (curr.children) {
      stack.push(...curr.children)
    }
  }
  return res
}