使用遞歸在二叉樹中找到鞍點

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

此代碼假設樹葉可以是鞍點，但調整它以排除這些節點並不難。