题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定。
解法一：
涉及到高度差，我们可以借鉴之前的题目“二叉树的深度”，通过判断每个节点左右子树的深度来得到判断高度差是否大于一。
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) {
return true;
}
int left = getDepth(root.left);
int right = getDepth(root.right);
if(left - right < -1 || left - right > 1) {
return false;
}
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
public int getDepth(TreeNode root) {
if(root == null) {
return 0;
}
int left = getDepth(root.left) + 1;
int right = getDepth(root.right) + 1;
return Math.max(left, right);
}
}
但是该程序在运行时，每个节点需要遍历很多次，性能很差。因为当判断根节点root时，其左子树和右子树的每个节点均要被遍历。当遍历root.left时，root.left的左右子树中的点又要再被遍历一遍……
解法二：
当我们采用倒序遍历来遍历二叉树时，便可以在遍历一个节点时已经得到其左右子树的深度，从而判断该节点是否满足平衡二叉树，自下向上地来判断是否为平衡二叉树。这样每个节点只需要被遍历一遍。
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
boolean[] flag = {true};
judgeTree(root, flag);
return flag[0];
}
public int judgeTree(TreeNode root, boolean[] flag) {
if(root == null) {
return 0;
}
int left = judgeTree(root.left, flag) + 1;
int right = judgeTree(root.right, flag) + 1;
if(left - right < -1 || left - right > 1) {
flag[0] = false;
}
return Math.max(left, right);
}
}
