小学生都能看懂的题解 | #判断是不是平衡二叉树#

什么是平衡二叉树？

平衡二叉树是一种特殊的二叉树，它的每一个节点的左子树和右子树的高度相差不会超过1。也就是说，如果我们从树的顶部开始看，每一层都不会相差太多。另外，空树也被认为是平衡的。

如何检查一棵树是否平衡？

我们要做的是检查树中的每一个节点，看看它的左右子树的高度差距是否超过了1。如果所有节点都符合这个规则，那么这棵树就是平衡的。

解决方案的步骤：

1. 定义一个方法 isBalanced：
1. 这个方法的主要任务是检查整棵树是否平衡。
2. 它接受树的根节点作为参数。
2. 定义一个辅助方法 checkHeight：
1. 这个方法用来计算节点的高度。
2. 如果发现某个节点的左右子树高度差距大于1，或者有一个子树已经不是平衡的，那么就返回一个特殊值 -1 表示不平衡。
3. 计算高度的方法：
1. 如果节点是 null（也就是空节点），那么它的高度是 0。
2. 否则，先递归地计算左子树的高度。
3. 如果左子树的高度已经是 -1，说明左子树不平衡，所以整个树也不是平衡的，返回 -1。
4. 接着计算右子树的高度。
5. 如果右子树的高度已经是 -1，说明右子树不平衡，返回 -1。
6. 然后比较左右子树的高度，如果差距大于 1，返回 -1。
7. 最后，返回两个子树中更大的高度加上 1 作为当前节点的高度。
4. 最终判断：
1. 如果 checkHeight 方法返回的不是 -1，说明树是平衡的，返回 true。
2. 如果返回 -1，说明树不是平衡的，返回 false。

示例代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // 主方法用来检查平衡性
    public boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }

    // 辅助方法用来获取树的高度，如果不平衡则返回-1
    private int checkHeight(TreeNode node) {
        if (node == null) {
            return 0; // 空节点的高度是0
        }

        int leftHeight = checkHeight(node.left); // 获取左子树的高度
        if (leftHeight == -1) return -1; // 如果左子树不平衡

        int rightHeight = checkHeight(node.right); // 获取右子树的高度
        if (rightHeight == -1) return -1; // 如果右子树不平衡

        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1; // 如果当前节点不平衡
        }

        return Math.max(leftHeight, rightHeight) + 1; // 返回当前节点的高度
    }
}

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。