二叉查找树的深度

Question

给定一个有序排列的数组写一个程序来找到一个深度最小的二叉搜索树，那么深度是多少？

我知道如何将数组转换为平衡BST，但是如何使函数创建最小深度的BST？

Answer 1

1）构建一个高度为h的完整二叉树（h是最小数字，例如2^h - 1> =数组中元素的数量）。此时您可以忽略输入数组。显然，这棵树具有最小深度（任何深度较小的树都不能有足够的节点来存储所有数组元素）。

2）现在你可以使用简单的递归方法填充这个数组元素：
i）填充左子树。
ii）将最小的未使用号码放入当前节点。
iii）填写正确的子树。
不要忘记在开始遍历之前删除2^h - 1 - n树叶（其中n是输入数组大小）（此步骤是必需的，因为完整树的大小为2^h - 1，但数组中只有n个元素）。

一个O(n)该算法的实现是非常有前途的（您可以明确地构建树，删除多余的树叶，然后遍历它，因为树中的节点数为O(n)）。