环境：python 3.6，scala 2.11.8
题意
N叉树的层次遍历，题意比较清晰，具体可戳此。
分析
虽然是 N 叉树遍历，仍可参考二叉树的先序、中序及后序遍历。
三种方法都使用递归和栈来完成二叉树的遍历，不同的是 N 叉树要求返回的结果为二维列表，反映节点间的层级关系。
递归
基于二叉树的通用递归写法，先来看看遍历 N 叉树的递归起手式：
def dfs(node):
if node:
# 符合某些条件后，添加至结果列表。类似于二叉树中的 rs.append(node.val)
for child in node.children: # 注意 node.children 为列表
dfs(child)
此时只用关心，将当前节点值添加到二维列表的哪个子列表中。
- 加一个标识节点层级的变量 depth，与最终返回的二维列表长度 rs 进行对比：
- 若 depth > len(rs)，则 rs 填充一维空列表；否则，添加当前节点值到 rs[depth] 即可；
- 换一个角度理解：二叉树遍历的对象是节点，而 N 叉树有层级要求，所以遍历的对象是携带自身层级关系的节点，或者是元组 (node, depth)。
栈
与二叉树不同的是，利用栈层次遍历 N 叉树，只需将当前访问的节点值添加至 rs 当前最后一个列表即可。具体见代码。
代码
python
def levelOrder(root):
"""
:type root: Node
:rtype: List[List[int]]
"""
rs = []
def dfs(node, depth):
if node:
while len(rs) <= depth:
rs.append([])
rs[depth].append(node.val)
for child in node.children:
dfs(child, depth+1)
dfs(root, 0)
return rs
def levelOrderV2(root):
if not root: return []
rs = []
stack = [root]
while stack:
rs.append([])
children = []
for node in stack:
rs[-1].append(node.val)
children += node.children
stack = children
return rs
scala
import scala.collection.mutable.{ListBuffer, Queue}
object LC429 {
def levelOrder(root: Node): List[List[Int]] = {
val rs = ListBuffer.empty[ListBuffer[Int]]
def dfs(node: Node, depth: Int): Unit = {
if (node != null) {
while (rs.length <= depth)
rs.append(ListBuffer[Int]())
rs(depth).append(node.value)
for (child <- node.children)
dfs(child, depth + 1)
}
}
dfs(root, 0)
rs.map(_.toList).toList
}
def levelOrderV2(root: Node): List[List[Int]] = {
if (root == null) return Nil
val rs = ListBuffer.empty[List[Int]]
val queue = Queue[Node](root)
while (queue.nonEmpty) {
val children = ListBuffer.empty[Node]
val elem = ListBuffer.empty[Int]
(1 to queue.size).foreach { _ =>
val node = queue.dequeue()
node.children.foreach{queue.enqueue(_)}
elem.append(node.value)
}
rs.append(elem.toList)
}
rs.toList
}
}
最后
欢迎交流及补充。
