Leetcode 110.平衡二叉树

力扣题目链接(opens new window)

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

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

解题思路：

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

思路解析：
要判断一个二叉树是否是平衡二叉树，需要满足以下条件：

1. 二叉树的左子树和右子树都是平衡二叉树。
2. 二叉树的左子树和右子树的高度差的绝对值不超过1。

可以使用递归的方式来解决这个问题。具体思路如下：

1. 编写一个辅助函数 getHeight，用于计算二叉树的高度。函数的输入是一个二叉树的根节点，返回值是该二叉树的高度。
2. 在 getHeight 函数中，首先进行一个判断，如果根节点为空，即整棵树为空树，那么它的高度为0，直接返回0。
3. 如果根节点不为空，那么分别递归计算左子树和右子树的高度，并取其中较大值，然后再加1（表示当前节点的高度），作为当前节点的高度值返回。
4. 接下来，编写主函数 isBalanced，用于判断给定的二叉树是否是平衡二叉树。主函数的输入是一个二叉树的根节点，返回值是一个布尔值表示是否是平衡二叉树。
5. 在 isBalanced 函数中，首先进行一个判断，如果根节点为空，即整棵树为空树，那么它是平衡的，直接返回 true。
6. 如果根节点不为空，那么分别递归判断左子树和右子树是否是平衡二叉树，并且判断左子树和右子树的高度差的绝对值是否超过1。
7. 如果左子树和右子树都是平衡二叉树，且高度差的绝对值不超过1，则整棵树是平衡的，返回 true；否则，返回 false。

通过递归地判断每个节点的左右子树是否平衡，并计算它们的高度差，可以判断整棵二叉树是否是平衡二叉树。

代码实现：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        // 如果根节点为空，则返回true，即空树是平衡的
        if (root == null) {
            return true;
        }
        // 获取左子树的深度
        int leftDepth = getHeight(root.left);
        // 获取右子树的深度
        int rightDepth = getHeight(root.right);
        // 判断左右子树的深度差是否大于1，如果大于1，则该树不是平衡二叉树，返回false
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return false;
        }
        // 递归判断左子树和右子树是否都是平衡二叉树
        return isBalanced(root.left) && isBalanced(root.right);
    }

    public int getHeight(TreeNode root) {
        // 如果根节点为空，则返回0，表示当前节点的深度为0
        if (root == null) {
            return 0;
        }
        // 递归计算左子树的深度
        int leftDepth = getHeight(root.left);
        // 递归计算右子树的深度
        int rightDepth = getHeight(root.right);
        // 返回左右子树深度的最大值加1，表示当前节点的深度
        return Math.max(leftDepth, rightDepth) + 1;
    }
}