LeetCode算法题-Balanced Binary Tree（Java实现）

佚名 6年前 (2018-11-11) 算法 719人围观抢沙发百度已收录

这是悦乐书的第167次更新，第169篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第26题（顺位题号是110）。给定二叉树，判断它是否是高度平衡的。对于此问题，高度平衡二叉树定义为：一个二叉树，其中每个节点的两个子树的深度从不相差超过1。例如：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

给定以下树[3,9,20，null，null，15,7]：

返回true。

给定以下树[1,2,2,3,3，null，null，4,4]：

返回false。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 解题

在昨天的那道题里，我们介绍了平衡树的概念，今天这道题也和平衡树有关，要判断一个二叉树是否为一颗平衡树，我们需要计算从根节点开始的左右子树的深度。

之前有道题是求二叉树的最长路径，如果没有印象的话可以找找历史文章。对于此题，可以借鉴那道题的思路，但是稍微有点不同，在拿到左子树和右子树的深度后，我们还要做下判断，看是否相差大于1，这一步在返回最后的深度前。

特殊情况：当二叉树为空时，他也是一颗平衡树。

public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    int dep = getDeepth(root);
    return dep >= 0;
}

public int getDeepth(TreeNode t){
    if (t == null) {
        return 0;
    }
    int left = getDeepth(t.left);
    int right = getDeepth(t.right);
    if (left == -1 || right == -1 || Math.abs(left-right)>1) {
        return -1;
    }
    return 1+Math.max(left, right);
}

如果left和right两数之差大于1，则返回-1，那么剩下没有遍历到的节点有可能等于-1，因此在前面还需要判断下left和right是否等于-1。