题解 | #判断是不是平衡二叉树#

基本思路

按照平衡二叉树的定义，需要一个函数来计算左右子树的深度，然后根据左右子树深度的差值是否不超过1判断是否为平衡二叉树，并且还要递归进入左右子树判断左右子树是否为平衡二叉树。

参考

参考题解

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    private int getTreeHeight(TreeNode pRoot) {
        // 空节点深度为0
        if (pRoot == null) {
            return 0;
        }
        // 递归获取左右子树的深度
        int leftHeight = getTreeHeight(pRoot.left);
        int rightHeight = getTreeHeight(pRoot.right);

        // 返回子树的最大深度加自己
        return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
    }
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here
        if (pRoot == null) {
            return true;
        }
        int left = getTreeHeight(pRoot.left);
        int right = getTreeHeight(pRoot.right);

        // 当前节点左右子树的高度差不能超过1
        if (left -right > 1 || right - left > 1) {
            return false;
        }

        // 同时左右子树又必须是平衡的
        return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
    }
}