0

我从朋友的采访中得到了这个问题：给定一棵二叉树，从靠近树中间的所有级别打印节点数组（最多两个节点）。这是一个例子：

    1 
   / \ 
  2 3 
/ \ \ 
4 5 9 
       / 
      10
输出是[ [2,3], [5,9], [10] ]。
我只能想到一个低效的方法：对树进行级别排序，对于每个级别，将当前级别的所有节点放入一个数组中，如果节点是NULL，则将一个标志（可能是 -1 或其他）放入插槽中。最后，打印出每个数组中间的所有节点。
对于上面的例子，我的代码将首先得到 4 个数组：
[1], [2,3], [4,5,-1,9],[-1,-1,10,-1]，在这个过程之后，打印出数组中所有不是 -1 的中间值。
我相信必须存在更好的解决方案，有人可以提供吗？谢谢！

4

3 回答 3

1

对于这个问题，我能想到的唯一方法是，从根开始，我们可以将节点分为两种类型：根的左侧和根的右侧。对于每一层，对于左侧节点，我们找到最右边的节点，对于右侧，我们找到最左边的节点。希望对你有帮助！

于 2013-10-03T04:30:10.570 回答
1

依次遍历树并保持节点的级别

节点：4-2-5-1-3-10-9

等级：2-1-2-0-1-3-2

现在对于level输出，我们从level 0开始，找到左边第一次出现的1——对应的数字是2，找到右边第一次出现的1——对应的数字是3，所以level 1的输出是< 2,3>

对 2 级输出做同样的事情是 <5,9>

3级输出只是<10>

时间复杂度 O(n) 空间复杂度 O(n)

与水平顺序遍历解决方案相同

于 2013-10-03T05:31:28.443 回答
0

在遍历树的所有元素之前，我们永远无法确定元素是否存在于第 i 层。因此，时间复杂度永远不会比 O(n) 更好，这与您提出的算法相同。

您的解决方案中唯一的问题是，对于每个级别，都需要维护一个单独的数组。尽管渐近地空间复杂度保持不变，但在绝对数量上它变成了额外的使用。

您可以执行以下操作：

  1. 做水平顺序遍历。
  2. 对于每个元素，当您将其推入队列时（用于级别顺序遍历），还要保持元素与中间的偏差。根的偏差为 0。根的左子节点的偏差为 -1。而右孩子将是+1。
  3. 对于每个级别，您需要保留一个“全局”元素，以了解元素与中间的接近程度。对于给定的级别，最多只能有 2 个元素。
  4. 对每个级别继续此操作。

该算法在稀疏树的空间复杂度方面工作得更好。

希望这可以帮助！

于 2013-10-03T04:34:45.813 回答