平衡二叉树深度

Question

当给定一定数量的节点时，我们可以通过执行log2(n)来计算二叉树的最小深度

其中n是节点数。

如果您绘制出树的最大深度，例如12个节点，那么如果树要保持平衡，则最大深度只能是4。

                0
               /   \
              0     0
            /  \   / \
           0    0 0   0
          /\     \     \ 
        0   0      0    0

很抱歉我的ascii艺术很糟糕。有没有人知道在给定节点数的情况下，能够计算出二叉树的最大深度的公式？或者至少给我指个正确的方向？

Answer 1

通过使用根元素 :

int maxHeight(BinaryTree *p) {
  if (!p) return 0;
  int left_height = maxHeight(p->left);
  int right_height = maxHeight(p->right);
  return (left_height > right_height) ? left_height + 1 : right_height + 1;
}

通过使用节点的数量和一些数学逻辑(我肯定不能正确地表达它(我绝不是数学专家)；但它在这里)：

观察:

• 2-3 nodes => maxDepth =1 (2 = 2^1，3= 2^1，..< 2^2 )
• 4-7 nodes => maxDepth =2 (4 = 2^2，5= 2^2，..，6= 2^2，..，7= 2^2，... < 2^3)
• 8-15 nodes => maxDepth = 3
• ...

分析:

• m =>最大深度(实际是深度的整数部分，去掉所有小数位)
• n =>节点数
• ln =>

(=loge)

• 2^m = n
• ln(2^m) = ln(n)
• m*ln(2) = ln(n)
• m = ln(n)/ln(2)

结论:

现在，如果m= 2，...，那么最大深度是2，只需得到它的int部分。;-)

备注：我肯定是在重新发明轮子；但这可能是处理一些你一无所知的事情的乐趣的一部分；并且只根据你的直觉和观察来做……:-)

Answer 2

最简单的答案看起来像这样：

int getMaxDepth(Node node)
{
    if(node == null) {
        return 0;
    }

    int leftDepth = 1 + getMaxDepth(node.left);
    int rightDepth = 1 + getMaxDepth(node.right);

    return left > right ? left : right;
}

概念explained

Answer 3

假设给定的节点数目(N)= 15公式is- log2n (以2为底的对数n)现在采用的最大值必须小于15，并且必须是2的幂结果。正如这里给出的15，no将为8。现在，n=8 log2(8)= 3，这是我们所需的答案