由一个数组构建高度最小的树

知识点：树的层数和高度和深度

首先要介绍树的层数：顶点的层数是从根到该顶点唯一通路的长度。

树的深度 = 层数

树的高度 = 层数 + 1

就拿这棵树来说

           10
          /  \
         6     14
        /     / \
       4    12   16

这棵树的高度是3，但深度是2。
顶点的高度与深度跟树的高度与深度是不同的，对于顶点的高度是从下往上计数的，可深度是从上往下计数的，就像是一栋大楼，我们说这栋大楼的高度是从下往上看的，而对于深度，可以看做树顶端的根顶点向下延伸的深度。这样就容易区分高度与深度了。比如拿值为14的顶点，它的高度是2，深度是1。

知识点：Python log() 函数

import math
math.log(x[, base])

x -- 数值表达式。
base -- 可选，底数，默认为 e
math.log(10,2) :  3.32192809489  
计算出来的结果是有小数的

思路：

平衡二叉树必定是最小高度的树；每一次的点数符合等比数列

import math


class MinimalBST:
    def buildMinimalBST(self, vals):
        # write code hereclass MinimalBST:
        n = len(vals)
        res = math.log(n+1,2)
        if res%1:
            return int(res)+1
        return int(res)

if __name__ == '__main__':
    va = [1,2,3,4,5,6,7]
    s = MinimalBST()
    res = s.buildMinimalBST(va)
    print(res)