剑指offer_【39】平衡二叉树

1.题目描述

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

2.解题思路

预备知识：平衡二叉树是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

思想：从根节点开始，先判断左右子树的高度差是否超过1，然后接着判断左右子树是否是平衡二叉树。这边用到了递归思想。

代码如下：

3.代码

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if( root == null) { //一棵空树就是平衡二叉树
            return true;
        }
        if( Math.abs(getDepth(root.left)  - getDepth(root.right)) <= 1 ) {
            //满足左右子树高度差小于等于1,那就接着判断左右子树是不是二叉树
            return (IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right));
        } else {
            //不满足左右子树高度差小于等于1,那这棵树肯定不是平衡二叉树啦
            return false;
        }
    }
    //递归求二叉树深度
    public int getDepth(TreeNode root) {
        if( root == null ) return 0;
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        return ( left > right ? left : right ) + 1;
    }

}