对二叉树中的元素进行排序
use*_*032 14 sorting algorithm binary-tree
这是我最近在接受采访时提出的一个问题.给出二叉树,其条件是每个左子项比根小1,右子项大1.这是一个示例树
以O(1)和O(n)时间复杂度对其进行排序.
以下是我建议的方法:
- 使用计数来维护每个元素的计数,然后在整个遍历完成O(n)时间和O(n)空间复杂度后返回.
- 使用行程编码.在以数字作为键重复元素并形成值时形成链.仅当没有重复时才需要空间进行计数,因此除了数组之外不需要额外的空间,但是时间复杂度将是O(n log n),因为我们必须遍历数组以查看它是否存在.
- 最后,我建议广度优先遍历.我们需要队列的O(log n)空间和O(n)时间复杂度(假设插入是O(1)链表).
你有什么办法？
小智 3
将给定树的某些叶节点修复为 NewHead 。
编写一个函数 Pop() 从给定的树中删除一些节点..！
编写弹出节点，以便仅在它存在时将其删除！等于 NewHead 。
因此，从树中弹出值，将其插入到以 New Head 作为头节点的新二叉搜索树中。
因此，您将从树中删除一个元素，并将其添加到新的搜索树中。
直到树头指向NewHead。
因此，所有元素现在都在二叉搜索树中，指向新头，这将是
显然是按顺序排列的。
这样可以保证您在 O(NlogN) 中进行排序。