[路飞]_leetcode-110-平衡二叉树

「这是我参与11月更文挑战的第4天，活动详情查看：2021最后一次更文挑战」

[题目地址][B站地址]

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

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

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

示例 1：

输入： root = [3,9,20,null,null,15,7]
输出： true
复制代码

示例 2：

输入： root = [1,2,2,3,3,null,null,4,4]
输出： false
复制代码

示例 3：

输入： root = []
输出： true
复制代码

提示：

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

根据题意，我们想要判断一个树是否是高度平衡的二叉树，就要对每一个子树判断左右子树的高度差的绝对值不超过1，所以这里我们通过递归进行该操作。

在递归向下的过程中求的每个子树的高度，回溯的过程中获取当前节点的左右子树的高度，判断高度差即可。

如果高度差大于1，这里我们的返回值有一个小技巧。

如果返回false,那我们在回溯的过程中就要处理返回值是非负整数还是 false 的情况，这会给我们带来额外的复杂度，我们这里可以利用当高度差大于1返回一个极大值这种技巧，来统一我们的返回值类型。

因为题意给我们一个信息是树的节点数范围是 [0, 5000] 内，所以这里返回 10000,也就是双倍的树高即可保证这个数值是肯定超过正常的树高的

至此，我们本题的解题思路就完成了，代码如下

var isBalanced = function(root) {
    function getHeight(root){
        if(root === null) return 0;
        const l = getHeight(root.left),
        r = getHeight(root.right);
        if(Math.abs(l-r)>1) return 10000;
        return Math.max(l,r)+1;
    }
    return getHeight(root)<10000
};
复制代码

至此，我们就完成了leetcode-110-平衡二叉树

如有任何问题或建议，欢迎留言讨论！