首页 文章

用于确定 balancer 二叉树的蛮力的运行时复杂性

提问于
浏览
0

我有以下蛮力方法的代码来确定二叉树是否 balancer :

public boolean IsBalanced(Node root)
{
  if (root == null) return true;
  return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
  && IsBalanced(root.left)
  && IsBalanced(root.right)
}

public int maxDepth(Node root)
{
  if (root == null) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

我不明白为什么当树是偏斜的树时,最坏情况的运行时复杂度是O(n ^ 2) . 我认为如果树是倾斜的,那么Math.abs(maxDepth(root.left) - maxDepth(root.right))<= 1行会立即发现根的左子树的高度结束比根右子树的高度多1个 . 然后,偏斜树案例的时间复杂度应为O(n) . 我在这里错过了什么?谢谢!

1 回答

  • 1

    在方法 IsBalanced(Node root) 中,首次调用时为偏斜树

    maxDepth(root.left) 它在 maxDepth(root) 中需要n个递归调用,现在仍然是

    IsBalanced(Node root) 中root不为null然后再调用它

    maxDepth(root.left) 现在为n-1次等等 . 所以时间复杂度是总和

    前n个自然数,即O(n ^ 2) .

相关问题