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

For example, given the tree:

例如,给定树:

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

The value returned by the function highestFull(BinaryNodeX<Comparable> *t) would be 3 as the height of the deepest full level is three.

函数highestFull(BinaryNodeX * t)返回的值将为3,因为最深满级别的高度为3。

1 个解决方案

#1

If a node has no left or right node, you know that the deepest full level is 1 - the node itself.

如果节点没有左或右节点,则您知道最深的完整级别为1 - 节点本身。

If it has left and right nodes, recurse and choose the smaller.

如果它有左右节点,则递归并选择较小的节点。

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

#1