常考数据结构与算法:平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（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;}}