题目描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
如下为平衡二叉树
如下为非平衡二叉树
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}public class IsBalancedTreeMe {public static void main(String[] args) {}public boolean IsBalanced_Solution(TreeNode root) {if(null == root){return true; // //一棵空树就是平衡二叉树}if(Math.abs(getDeep(root.left) - getDeep(root.right)) <= 1){// 左右子树的高度差小于等于1,那么接着判断左右子树是不是平衡二叉树return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);}else{//不满足左右子树高度差小于等于1,那这棵树肯定不是平衡二叉树return false;}}// 求树的高度private int getDeep(TreeNode root){if(null == root){return 0;}int left = getDeep(root.left);int right = getDeep(root.right);return (left > right ? left : right)+1;}}