590. N-ary Tree Postorder Traver

环境：python 3.6，scala 2.11.8

题意

N 叉树的后序遍历

分析

• 递归+栈；

• 可参考二叉树的后序遍历、N 叉树的先序遍历。

代码

python

def postorder(root):
    """
    :type root: Node
    :rtype: List[int]
    """
    rs = []

    def dfs(node):
        if node:
            for child in node.children:
                dfs(child)
            rs.append(node.val)
    dfs(root)
    return rs

def postorderV11(root):
    def dfs(node):
        if not node: return []
        rs = []
        for child in node.children:
            rs += dfs(child)
        rs.append(node.val)
        return rs

    return dfs(root)


def postorderV2(root):
    if not root: return []
    rs = []
    stack = [root]

    while stack:
        curr = stack.pop()
        rs.append(curr.val)
        stack.extend(curr.children)
    return rs[::-1]

scala

import scala.collection.mutable.{ListBuffer, Stack}

object LC590 {
  def postorder(root: Node): List[Int] = {
    val rs = ListBuffer.empty[Int]

    def dfs(node: Node): Unit = {
      if (node != null) {
        node.children.foreach(dfs)
        rs.append(node.value)
      }
    }

    dfs(root)
    rs.toList
  }

  def postorderV2(root: Node): List[Int] = {
    if (root == null) return Nil
    val rs = ListBuffer.empty[Int]
    val stack = Stack[Node](root)

    while (stack.nonEmpty) {
      val curr = stack.pop()
      rs.append(curr.value)
      curr.children.foreach(stack.push)
    }
    rs.toList.reverse
  }
}

最后

欢迎交流和补充