binary-tree - 在二叉树中查找 "local minimum"

Question

你们能帮我解决一些我被困的家庭作业问题吗？

完整二叉树中的局部最小值被定义为小于其所有邻居(邻居 = 父、左子、右子)的节点。
我需要在给定的完整二叉树中找到一个局部最小值，它的每个节点都有不同的数字，在 O(logn) 复杂度时间内。

好吧，由于要求是 O(logn)，所以我试图想一种方法，只通过 1 条路径穿过树到达一片叶子。
或者，也许我每次只能在递归中查看树的一半，这样它就会进行登录。

所以说我在树上有这个:

    70
   /  \
 77    60

有3种情况:

1)根比左右 child 都小//那么我就完成了

2) 根只比左边小

3) 根只比右边小

上面的树是情况 2。
所以让我们“扔掉”左子树，因为 77 不可能是“局部最小值”，因为它大于它的父级。
所以我们留下了右子树。依此类推，直到我们找到局部最小值。

这里的问题是，当我们抛出左子树时，我们可能会错过下面的另一个局部最小值。下面是一个例子:

                70
              /    \
            77      60
          /   \    /   \
         1    8    9    14
        / \  / \  / \   / \
       3   4 5 6  2 7  15 13

所以在这种情况下，唯一的局部最小值是“1”，但我们错过了它，因为一开始我们决定搜索根的右子树。

Answer 1

根据定义，局部最小值是一个节点，其值小于与其相连的任何其他节点的值。因此，在您的示例中，“1”、“5”、“6”、“2”、“7”、“13”都是局部最小值。

搞清楚了，问题就简单了。

首先我们检查根，看看它是否比两个 child 都小。如果是，那么我们就完成了。如果不是，那么我们拿起它的较小的 child 并递归地应用检查。

我们终止要么 1)我们发现一个比它的两个 child 都小的节点，要么 2)我们到达底层(即叶子)。

在情况 1) 中，我们停止的节点是局部最小节点，因为 i) 它小于它的两个子节点，并且 ii) 它小于它的父节点，这是我们决定检查这个节点的前提。

在情况 2) 中，我们留下了两个叶子(即 sibling )，并且其中至少一个比父节点小(否则将返回父节点)。然后，它们中的一个(或两个)都是局部最小值，只要它小于其父级即可。

按照这种方法，每个级别最多有 2 个节点被查看，因此只需要 O(log n) 检查。

希望这很有帮助并且足够清楚。