589. N-ary Tree Preorder Travers

环境：python 3.6，scala 2.11.8

题意

N 叉树的先序遍历

分析

与二叉树先序遍历类似，仍是基于递归或使用栈解决。不同的是遍历子节点的过程，先序会以从头至尾的顺序访问当前节点的 N 个子节点；后序则是逆序访问；

代码

python

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

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


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

    return dfs(root)


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

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

scala

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

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

    dfs(root)
    rs.toList
  }

  def preorderV2(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.length - 1 to 0 by -1).foreach(i => stack.push(curr.children(i)))
    }
    rs.toList
  }
}

最后

欢迎交流和补充