使用递归在二叉树中查找鞍点

Question

我想找到T的一个鞍点，二叉树，如果有的话。鞍点在其所有祖先中具有最小值，但在其所有后代中具有最大值。如果叶子的值低于其所有祖先的值，则叶子可以是这样的鞍点。

示例树：

              F:15
         E:16        H:17
    B:14         G:16    I:8
 A:8    C:7
           D:5

B是一个这样的鞍点，因为14小于16和15，但也大于8、7和5。A、C、D和I是其他鞍点。

我想办法递归检查每棵子树，证明父节点是所有后代节点中最大的。但是，由于C(16)是其所有后代中的最大值，但大于F(15)，所以不是鞍点，所以这种方法是不正确的。

最好的解决方法是什么？

Answer 1

编写一个函数 find_saddle 获取一个节点，以及 parent 的最小值（根节点默认为 INT_MAX）。它将return的值最大child。当函数被调用时，它计算出 a child 可以具有的最大值并且可能是一个鞍点，它本身的最小值和最小值 parent。然后，它以该最小值向左和向右递归，并在每个子树中接收最大值。如果该节点自身的值大于 bolth 子树的最大值但小于 parent 的最小值，那么它就是一个鞍点并且可以……为所欲为。最后，它 return 是它自己的值和两个子树最大值的最大值。

int find_saddle(node* n, int parent_min=INT_MAX) {
   int child_min = min(n->value, parent_min);

   int left_max = INT_MIN;
   if (n->left)
       left_max = find_saddle(n->left, child_min);

   int right_max= INT_MIN;
   if (n->right) 
       right_max = find_saddle(n->right, child_min);

   int child_max = max(left_max, right_max); 

   if (n->value > child_max && n->value < parent_min)
       do_thing(n);

   return max(child_max, n->value);
}

此代码假定叶子可以是鞍点，但调整它以排除这些节点并不难。

使用递归在二叉树中查找鞍点

Finding saddle point in a binary tree using recursion

algorithm

recursion

binary-tree