查找树

我从我朋友的这个问题采访的中间附近的所有节点：给定一个二叉树，从各级打印节点阵列（最多两个节点）附近树的中间。这里是一个例子：
查找树

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

来源

2013-10-03 DoReMi

设我问，如果节点10是9的正确孩子，那么第4行的答案仍然是10？因为我不明白为什么你必须将-1放入数组中。 –

@WorakarnIsaratham我很抱歉，我犯了一个错误，它仍然应该是[2,3]，[5,9]，[10]如果10是9的右子我把-1的原因是刚为纪念空节点，我可以把*或任何其他东西，以纪念插槽 – DoReMi

围棋中序遍历树，并保持该节点的水平

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

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

现在的电平输出，我们从0级开始，求1左侧第一次出现 - 相应的数目是2，找到的1的右侧第一次出现 - 相应的数字是3，所以电平1的输出< 2,3>

做同样的事情为水平2输出是< 5,9>

为3级输出只是< 10>

时间复杂性为O（n）空间复杂性为O（n）

同级别顺序遍历溶液

来源

2013-10-03 05:31:28

明白了，很好的解决方案！谢谢！ – DoReMi

我能想到的这个问题的唯一方法，从根本上，我们可以将节点分为两个类型：留根侧和根的右侧。而对于每一个级别，左侧的节点，我们找到了正确的最节点，和右侧，我们发现最左边的节点。希望对你有帮助！

来源

2013-10-03 04:30:10

你说得对，我分成两个部分的，然后平次序每个子树，不过，我觉得如果是这样，时间复杂度将是相同的，空间复杂度可能会提高。 – DoReMi

直到我们遍历树的所有元素之前，我们永远无法确定一个元素是否存在于第i层。因此，时间复杂度永远不可能优于O（n），这与您提出的算法相同。

解决方案中的唯一的问题是，对于每个级别需要一个单独的阵列，以进行维护。尽管渐近地空间复杂性保持不变，但绝对数量变得额外使用。

你可以做的是：

DO水平序遍历。
对于将每个元素推送到队列时（对于水平顺序遍历），还要保持元素与中间的偏差。根将有偏差为0.根的左孩子将有-1。而正确的孩子将是+1。
对于每个关卡，您都需要在元素到中间的距离附近保留一个“全局”元素。对于给定的级别，最多只能有2个元素。
继续为每个级别。

该算法的工作更好的空间复杂明智的稀疏的树木。

希望这有助于！

来源

2013-10-03 04:34:45

回答

相关问题