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

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，和我是其他鞍点。

我试着想办法递归地检查每个子树，并证明父节点是其所有后代中最大的。但是，由于C（16）在它的所有后代中是最大的，但是大于F（15），所以它不是鞍点，所以这种方法是不正确的。

什么是最好的解决方法。

Answer 1

编写一个功能find_saddle需要一个节点和父节点的最小值（默认为根节点的INT_MAX）。它会返回最大的孩子的价值。当函数被调用时，它会计算出孩子可能拥有的最大价值，并且可能是鞍，最小值和最小值。然后按照最小值向左和向右递归，并接收每个子树中的最大值。如果节点自己的值大于bolth子树的最大值，但小于父节点的最小值，那么它是一个鞍座，可以做任何你想要的。最后，它返回它自己的值和两个子树最大值的最大值。

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

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