题目描述

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

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

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

样例解释：

          1
        /   \
     2         3
   /  \     /  \
  4    5   6    7

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

数据范围：n ≤ 100,树上节点的val值满足 0 10000 ≤ n ≤ 1000

要求：空间复杂度O(1)，时间复杂度 O(n)

• 输入描述：输入一棵二叉树的根节点
• 返回值描述：输出一个布尔类型的值

示例

// 输入：
{1,2,3,4,5,6,7}
// 返回值：
true

// 输入：
{}
// 返回值：
true

解题思路

通过判断左右子树深度差（高度差）不大于1

因此，分别求解左右子树高度差即可

代码实现

/**
 * [JZ79-简单] 判断是否是平衡二叉树
 *
 * @param pRoot TreeNode类 
 * @return bool布尔型
*/
func isBalancedBinaryTree(pRoot *TreeNode) bool {
    return treeDepth(pRoot) > -1
}

func treeDepth(root *TreeNode) int {
    if nil == root {
        return 0
    }

    leftLength := treeDepth(root.Left);
    rightLength := treeDepth(root.Right);

    if -1 == leftLength || -1 == rightLength || 1 < abs(leftLength - rightLength) {
        return -1
    }

    return max(leftLength, rightLength) + 1
}

func abs(a int) int {
    if 0 > a {
        return -a
    }
    return a
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}