如何查找二叉查找樹中最深級別的高度？

Question

例如，給定的樹：

        10 
       5        15 
     0    6     12     20 // full 
-5  2    8     14   16   22 
      4            18    24 
                       26 

由函數highestFull(BinaryNodeX<Comparable> *t)返回的值將是3作爲最深滿液位的高度爲三個。

Answer 1

如果一個節點沒有左節點或右節點，則知道最深的最高級別爲1 - 節點本身。

如果它有左右節點，則遞歸併選擇較小的節點。

highestFull(BinaryNodeX<Comparable> *t) 
{ 
    if (! t->left || ! t->right) return 1; 
    return 1 + std::min(highestFull(t->left), highestFull(t->right)); 
}