平衡二叉树的检查

/**
 *实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不
 * 超过1。
 * 给定指向树根结点的指针TreeNode* root，请返回一个bool，代表这棵树是否平衡。
 */
           

import java.util.*;


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Balance {
    /**
     * 解决方法是使用递归，将问题单一化；
     * 将问题简单化为只需要求出左子树，右子树的高度，检查两者的差是否大于1
     * 在求子树高度时需要使用递归求解；同时也需要对根节点的遍历求解进行递归,判断是否每个节点都满足平衡
     * 只有所有节点都满足平衡才说明此树是一个平衡树
     *
     * @param root
     * @return
     */
    public boolean isBalance(TreeNode root) {

        if (root == null)
            return true;

        //获取左子树的高度
        int leftHeight = getHeight(root.left);
        //获取右子树的高度
        int righHeight = getHeight(root.right);
        //abs()返回绝对值
        if (Math.abs(leftHeight - righHeight) > 1){
            return false;
        }
		//对树节点进行遍历，判断是否所有节点都满足平衡
        return isBalance(root.left) && isBalance(root.right);
    }

	//求出子树的高度
    private int getHeight(TreeNode node){
        if (node == null)
            return 0;
        return Math.max(getHeight(node.left),getHeight(node.right)) + 1;
    }
}