题目描述

输入一棵节点数为 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
}

本文由 一切随风 创作,可自由转载、引用,但需署名作者且注明文章出处。

8 条评论

  1. rkzucejdfa
    rkzucejdfa

    超能一家人

  2. sxnvcdelpy
    sxnvcdelpy

    真爱找麻烦

  3. vtplstplmn
    vtplstplmn

    护国密探

  4. ptbabkiart
    ptbabkiart

    喜剧片的黄金时代

  5. bixvdtovvj
    bixvdtovvj

    人蛇大战李劲峰

  6. kdalecjkyn
    kdalecjkyn

    她说

  7. ppynlcrfow
    ppynlcrfow

    别碰脏钱

  8. mvgjaimuzu
    mvgjaimuzu

    真好呢

添加新评论