LeetCode 107.二叉树的层序遍历 II python/

Binary Tree Level Order Traversal II

环境：python 3.6，scala 2.11.8

题意

二叉树的层序遍历 II. 返回结果自底向上

分析

代码照贴，详见LC102-二叉树的层序遍历，思路相同；

代码

python

import collections

def levelOrderBottom(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 reversed(rs)


# 层次值作为键
def levelOrderBottomV2(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(), reverse=True)]


def levelOrderV3(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(), reverse=True)]

scala

import scala.collection.mutable.ListBuffer

object LC107 {
  def levelOrderBottom(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.reverse
  }

  def levelOrderBottomV2(root: TreeNode): List[List[Int]] = {
    if (root == null) return Nil
    var rs: List[List[Int]] = Nil
    val q = scala.collection.mutable.Queue[TreeNode](root)

    while (q.nonEmpty) {
      val elem = (1 to q.size).map {_ =>
        val curr = q.dequeue()
        List(curr.left, curr.right).filter(_ != null).foreach(q.enqueue(_))
        curr.value
      }.toList
      rs = elem :: rs
    }
    rs
  }

  def levelOrderBottomV3(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, List(currLevel.map(_.value)) ::: rs)
      }
    go(if (root == null) Nil else List(root), Nil)
  }
}

最后

欢迎交流和补充