描述

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

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

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

链接

BM36 判断是不是平衡二叉树 Nowcoder

示例

{1,2,3,4,5,6,7} => true
{} => true

题解

每个节点左右子树差 ≤ 1 → 平衡树

任意一个节点左右子树差 ＞ 1 → 非平衡树

代码思路：

定义一个求二叉树高度的函数depth，先处理特殊情况，空树，为平衡树

root为根节点的左右子树差 ≤ 1 → 继续向下判断子树是否满足条件，直到树中每个节点都判断完成 → 确定为一颗平衡二叉树

root为根节点的左右子树差 ＞ 1 → 非平衡

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pRoot TreeNode类
 * @return bool布尔型
 */
function IsBalanced_Solution(pRoot) {
    // write code here
    if (!pRoot) return true;
    const leftDepth = getDepth(pRoot.left);
    const rightDepth = getDepth(pRoot.right);
    if (Math.abs(leftDepth - rightDepth) > 1) {
        return false;
    }
    return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);

    function getDepth(tree) {
        if (!tree) return 0;
        const leftDepth = getDepth(tree.left);
        const rightDepth = getDepth(tree.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}
module.exports = {
    IsBalanced_Solution: IsBalanced_Solution,
};