《算法通关村—轻松搞定判断平衡树》

《算法通关村—轻松搞定判断平衡树》

描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true
1
2

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
1
2

示例 3：

输入：root = []
输出：true
1
2

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

理解

要判断一颗树是否平衡，就是要判断左右两颗子树的高度差是否大于1，这里如果两个子树的高度差大于1我们就返回-1，通过判断返回值是否大于等于0来判断是否是平衡树。

通过理解题目知道这个题是可以转化为更小的问题（比较两颗子树的高度差）来解决并且有结束条件，即转化为写递归函数。如果root等于null直接返回0，如果root不为null，那么就要比较两颗子树高度，首先得到leftHeight，和rightHeight，此时就要调用递归函数了，在他们自己递归的同时，他们可能直接判断出不是平衡树了，所以，等他们递归完，要有一个条件，判断leftHeight和rightHeight是不是-1并且他们俩之差是否大于1，如果是就直接返回-1结束，不是就是继续，返回高度最大的+1；

直接看代码

看代码，然后自己跟着递归来，可能能够好理解一点

public boolean isBalanced(TreeNode root) {
    return height(root) >= 0;
}
public int height(TreeNode root){
    if(root == null){
        return 0;
    }
    int left = height(root.left);
    int right = height(root.right);
    if(left == -1 || right == -1 || Math.abs(right-left) > 1){
        return -1;
    }
    return Math.max(left,right) + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

近期在自学 Java 做项目，加入了一个编程学习圈子，里面有编程学习路线和原创的项目教程，感觉非常不错。还可以 1 对 1 和大厂嘉宾交流答疑，也希望能对大家有帮助，扫 ⬇️ 二维码即可加入。

也可以点击链接：我正在「编程导航」和朋友们讨论有趣的话题，你⼀起来吧？

也可以加我QQ（2837468248）咨询说明来意！