Leetcode刷题100天—110.平衡二叉树(AVL树)—day05

喜欢ヅ旅行 2022-09-09 09:16 167阅读 0赞

前言：

> 作者：神的孩子在歌唱  
> 大家好，我叫运智

![image-20210816225806283][]

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

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

> 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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

> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/balanced-binary-tree  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package AVL树;
    /* * 1 * https://leetcode-cn.com/problems/balanced-binary-tree/ */
    public class _110_平衡二叉树 { 
    	public boolean isBalanced(TreeNode root) { 
    // 如果不是-1就返回true
            return height(root) != -1;
        }
    
        private int height(TreeNode node) { 
            if (node == null) return 0;
    // 通过递归，然后由底向上判断，先获取最后一个左子树的左右子树节点
            int leftHeight = height(node.left), rightHeight= height(node.right);
    // 因为如果存在一棵子树不平衡，则整个二叉树一定不平衡，我们通过左右子树相减，符合平衡条件是0,-1,1,如果高度差的绝对值大于1，说明不符合平衡，直接返回false
            if (leftHeight == -1 || rightHeight  == -1 || Math.abs(leftHeight - rightHeight) > 1)
                return -1;
    // 选择该节点左右子树中高度最高的加1返回,然后接着向上一个节点判断
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114  
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210816225806283]: /images/20220829/9c26f944b44a450f9e8b8260e3d64543.png