二叉搜索树的深度

Question

给定一个有序数组，编写一个程序来查找最小深度的二进制搜索树，那么深度是多少？

Answer 1

1. 构建一个高度为h的完整二叉树(h是使2^h - 1 >=数组中元素的最小数目)。此时，您可以忽略输入数组。显然，这个树有最小的深度(任何深度较小的树都不可能有足够的节点来存储所有的数组元素)。
2. 现在您可以使用一个简单的递归方法用数组元素填充这个树：

- Fill the left sub tree.  
- Put the smallest unused number into current node.   
- Fill the right sub tree.  

​

在开始遍历(其中n是输入数组大小)之前，不要忘记删除2^h - 1 - n叶(这一步是必要的，因为完整树的大小是2^h - 1，但是数组中只有n元素)。

这个算法的O(n)实现非常简单(您可以显式地构建树，删除多余的叶子，然后遍历它，因为树中的节点数是O(n)的)。