0

当给定多个节点时，我们可以通过 log2(n) 计算二叉树的最小深度

其中 n 是节点数。

如果你画出树的最大深度，例如 12 个节点，你会发现如果树要保持平衡，最大深度只能是 4。

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

对不起，糟糕的ascii艺术。有谁知道在给定节点数时能够计算二叉树最大深度的论坛？或者至少指出我正确的方向？

4

3 回答 3

3

通过使用根元素：

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 个节点 => 最大深度 = 1 (2 = 2^1, 3 = 2^1,.. < 2^2 )
  • 4-7 个节点 => 最大深度 = 2 (4 = 2^2, 5 = 2^2,.., 6 = 2^2,.., 7 = 2^2,... < 2^3)
  • 8-15 个节点 => 最大深度 = 3
  • ...

分析 ：

  • m => max Depth（实际是深度的 INT 部分，丢弃任何小数位）

  • n => 节点数

  • ln => 自然对数 (=log[e])

  • 2^m = n

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

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

结论 ：

现在，如果 m = 2,... ，则最大深度为 2。只需获取它的 int 部分。;-)

注意：我肯定在这里重新发明轮子；但这可能是处理你一无所知的事情的乐趣的一部分；并这样做，完全按照你的直觉和观察...... :-)

于 2012-03-23T11:11:34.817 回答
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;
}

概念解释

于 2013-07-13T19:21:43.027 回答
1

让节点数给定(n)=15 公式 is-log2n (log n base 2) 现在取一个最大值，该最大值必须小于 15，并且必须是 2 的幂结果。因为这里给出 15，所以 no 将是 8 . 现在，n=8 log2(8)= 3 ，这是我们需要的答案

于 2013-04-26T15:34:24.550 回答