问答

当前位置

93. Balanced Binary Tree

  • Ta: 陆助教

public boolean isBalanced(TreeNode root) {
// write your code here
if (root == null) {
return true;
}
int l = treedeep(root.left);
int r = treedeep(root.right);
if (isBalanced(root.left) && isBalanced(root.right) &&
(l == r || l == r - 1 || l == r + 1)) {
return true;
}
return false;
}
private int treedeep(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(treedeep(root.left), treedeep(root.right)) + 1;
}

    请问如果代码这样写时间复杂度是多少? 是N^2吗, N是node的个数。如果用九章答案里的returntype,时间复杂度是N?

1 个回复

2017-12-05 斌助教

首先九章的答案,每个节点只搜了一次,所以是O( n )的。
对于您的代码,每次搜到一个节点,还搜了一次这个节点子树的最深深度,所以是O( n^2 )的。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1