环境：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
}
}
最后
欢迎交流和补充
