题目描述
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左、右子树的深度相差不超过1,那么它就是一棵平衡二叉树。例如，图中的二叉树就是一棵平衡二叉树。
思路分析
在求二叉树的深度的过程中判断左右子树之间的高度差，如果高度差大于1 ，就返回-1，说明不是平衡二叉树，否则返回二叉树的深度。
测试用例
- 功能测试：平衡的二叉树;不是平衡的二叉树;二叉树中所有节点都没有左/右子树。
- 特殊输入测试：二叉树中只有一个节点;二叉树的头节点为nullptr指针。
Java代码
public class Offer055_02 {
public static void main(String[] args) {
test1();
test2();
test3();
}
public static boolean IsBalanced_Solution(TreeNode root) {
return Solution1(root);
}
private static boolean Solution1(TreeNode root) {
return getDepth(root)!=-1;
}
private static int getDepth(TreeNode root) {
if(root==null) return 0;
int leftDep = getDepth(root.left);
if(leftDep == -1) return -1;
int rightDep = getDepth(root.right);
if(rightDep==-1) return -1;
return Math.abs(leftDep-rightDep) >1 ? -1 :(Math.max(leftDep,rightDep) + 1);
}
private static void test1() {
}
private static void test2() {
}
private static void test3() {
}
}