我现在正在学习《程序员面试金典》这本书,并在做一道二叉树的练习题。书中给出的代码片段复杂度为 O(NlogN)
,但是我不明白为什么。如果算法复杂度是 O(N)
的话我能理解,但是我不知道他们的分析中哪里来的 logN
。
int getHeight(TreeNode root) {
if (root == null) return -1; // Base case
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
boolean isBalanced(TreeNode root) {
if (root == null) return true; // Base case
int heightDiff = getHeight(root.left) - getHeight(root.right);
if (Math.abs(heightDiff) > 1) {
return false;
} else {
// Recurse
return isBalanced(root.left) && isBalanced(root.right);
}
}
n
个节点的树,O(子树长度)就是O(n),对吗? - David G