如何找到二叉搜索树中最深层次的高度？

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