具有n个叶节点的二叉树的最小/最大深度是多少?

理想的“最深”的树。

 *
  *
   *
    *
     a 

该树显然包含一个叶节点,并且可以有无限多个中间节点。这意味着一个叶节点的最大深度是无界的(除非您的问题需要具有多个子节点的内部节点)

理想的“最浅”树

          *
      *       *
    *   *   *   *
   a a a a a a a a

这棵树显然含有 2^(depth-1) log(base2)(leaves) = depth-1 或 1+log(base2)(leaves) . 因为我们不能有一个分数深度,这必须与 ceil(1+log(base2)(leaves))

为了测试这一点,让我们构建一个表

leaves formula                        depth
  1    ceil(1+log(base2)(1)) => ceil(1+0) => ceil(1) => 1
  2    ceil(1+log(base2)(2)) => ceil(1+1) => ceil(2) => 2
  3    ceil(1+log(base2)(3)) => ceil(1+1.58) => ceil(2.58) => 3
  4    ceil(1+log(base2)(4)) => ceil(1+2) => ceil(3) => 3
  5    ceil(1+log(base2)(5)) => ceil(1+2.32) => ceil(3.32) => 4

因此,具有n个节点(其中n>0)的树的深度范围为

[ceil(1+log(base2)(n)), infinity)

除非最深的树上有更强的约束,比如“每个内部节点必须有两个兄弟节点(或类似的东西)”