确定平衡二叉树的蛮力算法的运行时间复杂度

Question

我有以下代码用于暴力方法，以确定二叉树是否平衡：

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(max depth(root . left)-max depth(root . right))行

Answer 1

在第一次调用倾斜树时的方法IsBalance（Node root）中

maxDepth（root.left） 在 maxDepth（root） 中需要 n 个递归调用，现在仍然是

root 在 IsBalanced（Node root） 中不为空，然后再次调用

< code>maxDepth(root.left)现在进行n-1次，以此类推，所以时间复杂度是

前n个自然数，即O（n^2）。