[腾讯笔试]在完整的二进制排序树中找到三个节点中最小子树的根节点

标题: 完整的二进制排序树的深度为k，节点数为2 ^ k-1；给定k值和任何三个节点，则节点值为1到（2 ^ k-1），输出包含三个节点中最小子树的根节点. 样本输入: 4 10 15 13样本输出: 12

首先，让我们了解完整二进制排序的数量. 以下是4级完整的二进制排序树:

*          8
*        /   \
*       4     12
*      / \   /   \
*     2  6   10   14
*    /\  /\  / \ /  \
*   1 3 5 7 9 11 13 15

从上图可以看到，完整的二进制排序树的中阶遍历是从1到2 ^ k-1的递增序列（k是层数）. 因此，只要给出层数，我们就可以确定二进制排序树. 同时二叉排序树的查找，从观察结果可以看出，二元排序树从上到下的根节点只是所有元素二元搜索的中间节点. 根据上述规则，为解决三节点最小子树的根节点问题，可以得到以下几点: 无需建立二叉树，从1?2 ^ k-1递增数组是输入时完整的二叉排序树当三个元素在二分法节点的两侧时，当前二分法节点是要找到的最小子树的根节点（根据此规则，我们不需要判断这三个元素，只需确定最大元素和最小元素的位置即可）当最小节点的值大于二分法节点的值时，继续在二分法的右半部分搜索. 当最大节点的值小于二分法节点的值时，请继续在二分法的左半部分搜索. 根据以上节点二叉排序树的查找，编写代码如下:

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-249778-1.html