找到给定数组前序表示的 BST 树的高度

Question

上图示例。数组表示 is:8,3,1,6,4,7,10,14,13 我想在不构建树的情况下找出高度....... 基本上你有 BST 的数组表示你需要在不构建树的情况下找出树的高度？

Answer 1

这个问题可以用递归的方法来解决，因为大多数树问题都解决了。

伪代码-

int get_height(int a[], int low, int hi) {
   if(low > hi)
      return -1;

   int root = a[low];

   // Find position pos in the range (low+1) to hi such that 
   // all elements at left of pos are <= root and all elements at right 
   // of pos are > root. Do this using modified binary search

   int pos = <position for root found as described above>

   int ht = 1 + max (get_height(a, low+1, pos),
                     get_height(a, pos+1, hi));

   return ht;
}