LeetCode 987.二叉树的垂序遍历 python/sca

环境：python 3.6，scala 2.11.8

题意

二叉树的垂序遍历：

• 假设某节点坐标为，则其左右子节点坐标为、；
• 返回二维列表，坐标相同的节点会被添加至同一个子列表；
• 坐标完全相同的节点，优先添加较小值；
• 二维列表中子列表之间的顺序是以升序返回；
• 树的节点数范围 ，节点值范围；

分析

• 注意：至少掌握二叉树的前中后三种遍历方式的其中一种；
• 思路：遍历二叉树，将节点值及其坐标添加至集合。再按坐标排序得到最终结果；
• 方法：
  • 由题意可知，中序遍历方式更合适；
  • 遍历方法可选择递归或迭代；
  • 常见的用列表装载节点值及其坐标，Python 中也可使用 ；
  • 排序方式为按升序、降序、节点值升序；便于编程，这里也可以假设节点坐标为的左右子节点坐标为、，这样都能默认以升序排序。具体排序细节根据集合的选用而异；
• 题中给定的节点数和节点值条件，详见代码细节；

代码

python

import collections


# 中序遍历，按垂线树深双属性顺序加载
def verticalTraversal(root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    if not root: return []
    rs = []

    def dfs(node, x, y):
        if node:
            dfs(node.left, x - 1, y + 1)
            rs.append((x, y, node.val))
            dfs(node.right, x + 1, y + 1)

    dfs(root, 0, 0)
    # 若这里装载元素为(val, x, y)，则用 python 多属性排序会超时
    rs.sort()
    res = []

    minimum = -1001 # 极限情况下节点值不会小于 -1000
    for x, y, val in rs:
        if x != minimum:
            res.append([])
            minimum = x
        res[-1].append(val)
    return res


# 中序遍历，同一垂线按树深顺序加载
def verticalTraversalV2(root):
    if not root: return []
    d = collections.defaultdict(list)

    def dfs(node, x, depth):
        if node:
            dfs(node.left, x - 1, depth + 1)
            d[x].append((depth, node.val))
            dfs(node.right, x + 1, depth + 1)

    dfs(root, 0, 0)
    res = []
    for key in sorted(d.keys()):
        d[key].sort()
        res.append([e[1] for e in d[key]])
    return res


# 同上
def verticalTraversalV3(root):
    """
    :param root:
    :return:
    """
    if not root: return []

    stack = [(root, 0, 0)] # 节点，x坐标, 深度
    d = collections.defaultdict(list)

    while stack:
        children = []
        for node, x, depth in stack:
            if node:
                d[x].append((depth, node.val))
                children.append((node.left, x - 1, depth + 1))
                children.append((node.right, x + 1, depth + 1))
        stack = children

    res = []
    for key in sorted(d.keys()):
        d[key].sort()
        res.append([e[1] for e in d[key]])
    return res

scala

import scala.collection.mutable.ListBuffer

object LC987 {
  /** 这里提交后超时了，可参考第二种写法*/ 
  def verticalTraversal(root: TreeNode): List[List[Int]] = {
    val rs = ListBuffer.empty[(Int, Int, Int)]

    def dfs(node: TreeNode, x: Int, y: Int): Unit = {
      if (node != null) {
        dfs(node.left, x - 1, y + 1)
        rs.append((x, y, node.value))
        dfs(node.right, x + 1, y + 1)
      }
    }

    dfs(root, 0, 0)

    val res = ListBuffer.empty[ListBuffer[Int]]
    var minimum = -1001

    for ((x, _, value) <- rs.sortBy(e => (e._1, e._2))) {
      if (x != minimum) {
        res.append(ListBuffer.empty[Int])
        minimum = x
      }
      res.last.append(value)
    }
    res.map(_.toList).toList
  }

  case class Node(x: Int, depth: Int, value: Int)

  def verticalTraversalV2(root: TreeNode): List[List[Int]] = {
    def dfs(node: TreeNode, x: Int, depth: Int): List[Node] =
      if (node == null) List.empty[Node]
      else dfs(node.left, x - 1, depth + 1) ::: List(Node(x, depth, node.value)) ::: dfs(node.right, x + 1, depth + 1)

    val nodes = dfs(root, 0, 0)

    nodes.groupBy(_.x).toList sortBy(_._1) map { case (_, nod) =>
      nod.sortBy(neighbor => (neighbor.depth, neighbor.value)).map(_.value)}
  }
}

最后

欢迎交流和补充