字节考过的面试题！你真的会吗？110. 平衡二叉树(含不同解法)

字节考过的面试题！你真的会吗？110. 平衡二叉树(含不同解法)

引用

CSDN

1.

https://blog.csdn.net/2301_79417489/article/details/145522832

本文将详细介绍如何判断一个二叉树是否是平衡二叉树，包括暴力求解和优化解法两种方法。通过本文的学习，你将能够掌握平衡二叉树的判断方法，并能够编写相应的代码实现。

第一次做不用力求优化，没能力优化就先暴力解题，等能暴力解出来再递进到优化。

题目链接： 110. 平衡二叉树

题目： 给定一个二叉树，判断它是否是 平衡二叉树。

解法一：暴力求解O(N^2)

暴力解法的思路 ：对于每个节点，计算其左右子树的高度，检查高度差是否超过1。如果所有节点都满足这个条件，那么整个树就是平衡的。
但这个方法的时间复杂度很高，因为每个节点的高度会被重复计算多次。例如，对于根节点，需要计算左右子树的高度，而这两个子树的高度计算又会递归到底层节点，导致时间复杂度为O(n^2)，这在节点数较多时效率不高。

1. 核心思路

暴力求解的思路不会通过，会超时。

step1. 平衡二叉树定义

判断是否为平衡二叉树，需 同时满足 以下条件：

1. 每个节点 的左右子树的高度差不超过1
2. 每个节点 的左右子树本身也是平衡二叉树

step2. 实现要点

1. 定义一个方法用于求树的高度。
2. 递归遍历树的每个节点。
3. 求每个节点的左右子树各自的高度，判断是不是平衡二叉树。

2. 细化要点

2.1 定义一个方法用于求树的高度。

//求一棵树的高度
    private int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }

        int leftCount = maxDepth(root.left);
        int rightCount = maxDepth(root.right);

        return Math.max(leftCount,rightCount) + 1;
    }

2.2 终止条件(平衡二叉树的定义)

1. 节点为null，返回true。

    //空树
        if (root == null){
            return true;
        }
   

2. 每个节点的左右子树的高度差超过1，返回false。

     //求出左右子树高度的最大值
        int depth = Math.abs(maxDepth(root.left)-maxDepth(root.right));
        //左右子树的高度差不超过1
        if (depth > 1){
            return false;
        }
   

3. 左右子树本身是平衡二叉树，返回true。

    //左右子树本身也是平衡二叉树
        return isBalanced(root.left) && isBalanced(root.right);
   

解法二：优化O(N)

高度重复求，导致复杂度过高，优化从减少重复计算高度入手。那就计算高度的同时判断是否平衡。在求高度的方法内加上判断语句即可。

【代码演示】

class Solution {
    public boolean isBalanced(TreeNode root) {
        //空树
        if (root == null){
            return true;
        }
        return maxDepth(root) != -1;
    }

    //求一棵树的高度
    private int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }

        int leftCount = maxDepth(root.left);
        if (leftCount == -1){
            return -1;
        }
        int rightCount = maxDepth(root.right);
        if (rightCount == -1 ||Math.abs(leftCount - rightCount) > 1){
            return -1;
        }
        return Math.max(leftCount,rightCount) + 1;
    }
}