11.树的挑战¶

挑战1：按级别顺序打印一棵树¶

根据树的级别，按顺序打印树中的所有值。同一级别的节点应打印在同一行。例如，考虑下面这棵树：

你的算法应该打印如下：

15
1 17 20
1 5 0 2 5 7

Tips

考虑使用启动Playground的Sources文件夹中为你提供的Queue。

挑战2：父类和所有权¶

考虑一下树节点的原始定义：

public class TreeNode<T> {
  public var value: T
  public var children: [TreeNode] = []

  public init(_ value: T) {
    self.value = value
  }
}

你如何修改这个定义以包括父母？关于所有权，你应该做哪些考虑？

解决方案¶

挑战1的解决方案¶

按等级顺序打印节点的简单方法是利用Queue数据结构来进行等级顺序遍历。棘手的地方是确定什么时候应该出现换行。这里是解决方案：

func printEachLevel<T>(for tree: TreeNode<T>) {
  // 1
  var queue = Queue<TreeNode<T>>()
  var nodesLeftInCurrentLevel = 0
  queue.enqueue(tree)

  // 2
  while !queue.isEmpty {

    // 3
    nodesLeftInCurrentLevel = queue.count

    // 4
    while nodesLeftInCurrentLevel > 0 {
      guard let node = queue.dequeue() else { break }
      print("\(node.value) ", terminator: "")
      node.children.forEach { queue.enqueue($0) }
      nodesLeftInCurrentLevel -= 1
    }

    // 5
    print()
  }
}

你首先初始化一个Queue数据结构，以便于水平顺序的遍历。你还创建了nodesLeftInCurrentLevel来跟踪你在打印新行之前需要处理的节点的数量。
你的级别顺序遍历继续进行，直到你的队列为空。
在第一个while循环中，你首先将nodesLeftInCurrentLevel设置为队列中的当前元素。
使用另一个while循环，你从队列中取出第一个nodesLeftInCurrentLevel数量的元素。每一个脱队的元素都被打印出来，而不需要建立一个新的行。你也要排队等待该节点的所有子节点。
在这一点上，你使用print()生成新行。在下一次迭代中，nodesLeftInCurrentLevel将被更新为队列的计数，代表上一次迭代中的子节点数量。

这个算法的时间复杂度为O(n)。由于你初始化了Queue数据结构作为一个中间容器，这个算法也使用了O(n)空间。

挑战2的解决方案¶

你可以给TreeNode增加一个属性parent，像这样：

public class TreeNode<T> {

  public weak var parent: TreeNode?

  // etc...
}

使用一个可选的类型，因为根节点没有一个父节点。赋予它弱所有权以避免引用循环。按照惯例，一个节点与它的子节点有强所有权关系，但与它的父节点有弱非所有权关系。继续链接列表的类比，有父节点的节点类似于一个双链接列表。有更多的簿记开销需要担心，但它允许快速向上遍历树。