一棵排序二叉树，令 f=(最大值最小值)2，设计一个算

[问答题]

一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n² )则不得分。

李程鹏

1：先找到值最小的节点，用O(h)的复杂度，h是值最小节点的高度 2：从最小的节点开始，依次找到当前节点的successor，然后把successor设置为当前节点，一直到当前节点大于f时，停止寻找 3：因为这个算法最多遍历边2次，变的数量比节点的数量小1，所以复杂度是O(n)

发表于 2018-01-27 17:03:59 回复(0)

北方有佳人zz

1. 遍历根的右子树，一直右到底即可找到最大值（or 最小值），时间复杂度O(logn)。

2. 遍历根的左子树，一直左到底即可找到最小值（or 最大值），时间复杂度O(logn)。

3. 通过计算得出 f，从根节点开始执行二分查找的过程，找到第一个大于当前节点的值的节点，记录下这个节点以及这个节点与 f 的差，循环判断当前节点是否有左子树（右子树肯定比当前节点还大，离 f 就更远了），判断左子树节点的值如果大于 f 并且与 f 的差值小于当前的这个差值，就记录下这个节点，直到左子树为空，返回保存的大于 f，并且与 f 的差值最小的那个节点，时间复杂度O(logn)。

总结：总体时间复杂度O(logn)。

编辑于 2018-03-23 17:19:48 回复(0)