q****x
发帖数: 7404 | 1 这个递归解法简洁但低效。应该用DP，在hash table里把每个节点和子树深度记下来？
int getHeight(Node* root)
{
if (root === NULL) return 0;
return max(getHeight(root->left), getHeight(root->right)) + 1;
}
bool isAVL(Node* root)
{
if (root == NULL) return true;
return abs(getHeight(root->left) - getHeight(root->right)) <= 1
&& isAVL(root->left) && is AVL(root->right);
} | s******n
发帖数: 3946 | 2 bool isAVLTree(Node* n, int* height)
{
if (n==NULL) {
*height = 0;
return true;
}
int left_height, right_height;
if (isAVLTree(n->left, &left_height) && isAVLTree(n->right, &right_height) && abs(left_height-right_height)<=1) {
*height = max(left_height, right_height)+1;
return true;
} else {
return false;
}
} |
|
