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

Question

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

3

如果存在的话，我想要找到T的一个鞍点(binary tree)。鞍点的值在其所有祖先中是最小的，在其所有后代中是最大的。如果叶子节点的值比其所有祖先都要低，那么它可以是这样的鞍点。

示例树:

              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），因此这种方法是不正确的。

那么解决它的最佳方法是什么？

- BBbbBB

A、B、C和I都是鞍点。 - BBbbBB

是的，A、B、C、I、D。抱歉。 - BBbbBB

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mooing Duck · Accepted Answer

编写一个函数find_saddle，它接受一个节点和父节点的最小值（默认为根节点的INT_MAX）。函数将返回最大子节点的值。当调用函数时，它确定一个孩子可能具有的最大值，并且可能是马鞍的最小值为自身和最小父节点。然后，它使用该最小值递归向左和右下降，并在每个子树中接收最大值。如果节点自己的值大于两个子树的最大值但小于父节点的最小值，则它是马鞍并执行...您想要的任何操作。最后，它返回自己的值和两个子树最大值中的最大值。

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);
}

这段代码假设叶子节点可以是鞍点，但是将其调整为排除这些节点并不是很困难。