当前位置：网站首页>leetCode刷题14天二叉树系列之《 110 平衡二叉树判断》

leetCode刷题14天二叉树系列之《 110 平衡二叉树判断》

2022-08-11 03:42:00 【小机double】

leetCode 110 平衡二叉树判断

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例

给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4

题目解析

与平衡二叉树等基础相关的可以看《数据结构之二叉树和平衡二叉树的实现》，根据题目的意思，我们需要对每个节点判断其左右子树的高度，并保证其高度差不超过1，即每个节点的平衡因子不超过1，如果查过1的话就不是平衡二叉树了，此时就要进行平衡化操作，不过这并不属于本题要讲述的内容。

其实只要使用递归的方式，并统计左右子树的高度来比较即可，代码如下：

class Solution {
    
    public boolean isBalanced(TreeNode root) {
    
        if (root == null) {
    
            return true;
        }

        if (!isBalanced(root.left) || !isBalanced(root.right)) {
    	//如果有左右子树不满足平衡二叉树条件则返回false
            return false;	
        }

        int leftDepth = maxDepth(root.left) + 1;
        int rightDepth = maxDepth(root.right) + 1;
        if (Math.abs(leftDepth - rightDepth) > 1) {
    
            return false;
        }
        return true;
    }

    public int maxDepth(TreeNode root) {
    	//计算每颗树的最高深度
        if (root == null) {
    
            return 0;
        }
        if (root.left == null && root.right == null) {
    
            return 1;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}