我有以下蛮力方法的代码来确定二叉树是否 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 回答
在方法
IsBalanced(Node root)
中,首次调用时为偏斜树maxDepth(root.left)
它在maxDepth(root)
中需要n个递归调用,现在仍然是在
IsBalanced(Node root)
中root不为null然后再调用它maxDepth(root.left)
现在为n-1次等等 . 所以时间复杂度是总和前n个自然数,即O(n ^ 2) .