AVL树的定义：
1）空树
2）左子树和右子树的高度差的绝对值<=1
public boolean isAVLTree(BinaryTreeNode root) {
if (root == null) {
return true;
}
System.out.println(root.value);
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (Math.abs(leftHeight - rightHeight) > 1) {
return false;
}
if (root.left != null && !isAVLTree(root.left)) {
return false;
}
if (root.right != null && !isAVLTree(root.right)) {
return false;
}
return true;
}
private int height(BinaryTreeNode root) {
if (root == null) {
return 0;
}
return Math.max(height(root.left), height(root.right)) + 1;
}
这是我的第一版代码，思路是对二叉树做先序遍历，对每棵树求高度。
但主逻辑略显拖沓，这是 condition1 && condition2 && condition3的逻辑。
所以代码可以写得更加精炼：
public boolean isAVLTree(BinaryTreeNode root) {
if (root == null) {
return true;
}
System.out.println(root.value);
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.abs(leftHeight - rightHeight) <= 1 && isAVLTree(root.left) && isAVLTree(root.right);
}
上述代码存在什么问题吗？
问题是显而易见的，就是存在着大量的重复计算。时间复杂度是O(N^2).
那么存在着更简单的方法吗？
static class Height {
int h;
}
public boolean isAVLTree(BinaryTreeNode root, Height height) {
if (root == null) {
return true;
}
Height leftHeight = new Height();
Height rightHeight = new Height();
boolean ret = isAVLTree(root.left, leftHeight);
if (!ret) {
return false;
}
ret = isAVLTree(root.right, rightHeight);
if (!ret) {
return false;
}
if (Math.abs(leftHeight.h - rightHeight.h) > 1) {
System.out.println(root.value);
return false;
}
height.h = Math.max(leftHeight.h, rightHeight.h) + 1;
return true;
}
常见的递归的是上层去改变下层的数据，而这段代码却是用下层改变上层数据。
把逻辑&拆开写，这样可以在它们中间插入代码。
这样只需要遍历一次节点即可，算法复杂度是O(N)。
上层获取下层的值往往是用return返回结果，此外就是引用。这道题目除了要返回boolean还有height，能不能返回两值呢？答案是肯定的——封装。
static class Result {
boolean ret = true;
int h;
}
public Result isAVLTree(BinaryTreeNode root) {
if (root == null) {
return new Result();
}
Result leftResult = isAVLTree(root.left);
if (!leftResult.ret) {
return leftResult;
}
Result rightResult = isAVLTree(root.right);
if (!rightResult.ret) {
return rightResult;
}
Result result = new Result();
result.h = Math.max(leftResult.h, rightResult.h) + 1;
result.ret = Math.abs(leftResult.h - rightResult.h) <= 1;
return result;
}
2019-03-20阅：
现在觉得把引用当成参数传进来写的做法不好，要么设置全局变量，要么封装多个返回值。注意第一段代码和第三段代码的比较。
2019-07-18
二叉树是最好的递归数据结构典范。写递归程序需要注意
- 递归的边界
- 递归每层之间的联系
- 递归的基本单元。复杂递归就是它们的组合。
2020-02-21
Result isAVL(BinaryTreeNode root) {
if (root == null) {
return new Result(0, true);
}
Result leftChild = isAVL(root.left);
Result rightChild = isAVL(root.right);
int height = 1 + Math.max(leftChild.height, rightChild.height);
boolean ret = leftChild.ret && rightChild.ret && Math.abs(leftChild.height - rightChild.height) <= 1;
return new Result(height, ret);
}
看上去更精简，实际上存在多余计算，如果左子树不是AVL树，那么没有必要计算右子树了。不过如果想获得树的高度，非这么写不可。
