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