LeetCode 102.二叉树的层序遍历 python/sca

环境：python 3.6，scala 2.11.8

题意

按二叉树的层次/深度遍历，自上而下，从左到右。

分析

相关分析可移步至 N 叉树的层次遍历，解法思路相同。
区别在于本题 Python 解法二和解法四中用到了值类型为列表的字典，以及 Scala 解法3的写法有所变化。

代码

python

import collections


def levelOrder(root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    if not root: return []
    rs = []

    def dfs(node, depth):
        if node:
            while len(rs) <= depth:
                rs.append([])
            rs[depth].append(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

    dfs(root, 0)
    return rs


# 层次值作为键
def levelOrderV2(root):
    if not root: return []
    d = collections.defaultdict(list)

    def dfs(node, depth):
        if node: # 先中后序都可
            d[depth].append(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

    dfs(root, 0)
    return [d[key] for key in sorted(d.keys())]


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

    while stack:
        rs.append([])
        children = []
        for node in stack:
            if node:
                rs[-1].append(node.val)
                children.append(node.left)
                children.append(node.right)
        stack = children
    return rs if rs[-1] else rs[:-1]


def levelOrderV4(root):
    if not root: return []
    d = collections.defaultdict(list)
    stack = [(root, 0, 0)] # 节点，深度，是否已被访问

    while stack:
        curr, x, visited = stack.pop()
        if curr:
            if visited:
                d[x].append(curr.val)
            else: # 因为同一层节点只要左先于右被添加即可，所以这里先中后序都可以
                stack.append((curr.right, x + 1, 0))
                stack.append((curr, x, 1))
                stack.append((curr.left, x + 1, 0))
    return [d[key] for key in sorted(d.keys())]

scala

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

object LC102 {
  def levelOrder(root: TreeNode): List[List[Int]] = {
    val rs = ListBuffer.empty[ListBuffer[Int]]

    def dfs(node: TreeNode, depth: Int): Unit = {
      if (node != null) {
        while (rs.length <= depth)
          rs.append(ListBuffer.empty[Int])
        rs(depth).append(node.value)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
      }
    }

    dfs(root, 0)
    rs.map(_.toList).toList
  }

  def levelOrderV2(root: TreeNode): List[List[Int]] = {
    if (root == null) return Nil
    val rs = ListBuffer.empty[List[Int]]
    val queue = Queue[TreeNode](root)

    while (queue.nonEmpty) {
      val elem = ListBuffer.empty[Int]
      (1 to queue.size).foreach{_ =>
        val curr = queue.dequeue()
        if (curr.left != null) queue.enqueue(curr.left)
        if (curr.right != null) queue.enqueue(curr.right)
        elem.append(curr.value)
      }
      rs.append(elem.toList)
    }
    rs.toList
  }

  def levelOrderV3(root: TreeNode): List[List[Int]] = {
    def go(currLevel: List[TreeNode], rs: List[List[Int]]): List[List[Int]] =
      if (currLevel.isEmpty) rs
      else {
        val nextLevel = currLevel.flatMap{node => List(node.left, node.right).filter(_!=null)}
        go(nextLevel, rs :+ currLevel.map(_.value))
      }
    go(if (root == null) Nil else List(root), Nil)
  }
}

最后

欢迎交流和补充