平衡二叉树

╰+攻爆jí腚メ 2023-10-14 16:04 1阅读 0赞

**目录**

题目

示例

示例 1：

示例 2：

示例 3：

提示:

1.树中的节点数在范围 \[0, 5000\] 内

2.-104 <= Node.val <= 104

题解

1.初创代码

2.运行结果

3.代码执行图示

4.时间复杂度

代码问题

1.存在重复计算

2.当不满足条件时,没有立即终止,递归仍在进行

难度提升 (字节面试题)

(1) 面试官题问:能否以以O(n)的时间复杂度完成该问题?

(2)思路: 求高度的过程中,就判断是否平衡

(3)代码如下

(4)运行结果

(5)代码执行图示

(6)代码略微改动

(7)图解

完结撒花,宝子们动动你发财的小手给博主点个关注吧!!!爱你们(＾Ｕ＾)ノ~ＹＯ

--------------------

## 题目 ##

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

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

> 一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过 1 。

### 示例 ###

#### **示例 1：** ####

![a666e9274c28441ab4924860211db197.jpeg][]

>  **输入：root = \[3,9,20,null,null,15,7\]  
> 输出：true**

#### **示例 2：** ####

![6b75e3e28f1443098a41f7d95e25e072.jpeg][]

>  **输入：root = \[1,2,2,3,3,null,null,4,4\]** 
> 
>  **输出：false**

#### **示例 3：** ####

> 输入：root = \[ \]
> 
> 输出：true

#### 提示: ####

##### **1.树中的节点数在范围 `[0, 5000]` 内** #####

##### **`2.-104 <= Node.val <= 104`** #####

## 题解 ##

### 1.初创代码 ###

public class Solution {
        public int findHeightTree(TreeNode root) {//求高度的方法
            if (root == null) {
                return 0;//root为null不存在节点,高度为0
            }
            /*if (root.left == null && root.right == null) {
                return 1;//root的孩子节点都为空的时候,root只存在一个节点,高度为1
            }*///这段代码可以省略
            int leftTreeHeight = findHeightTree(root.left);//求root左子树的高度
            int rightTreeHeight = findHeightTree(root.right);//求root右子树的高度
            return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1 : rightTreeHeight + 1;
            //该root节点的高度=leftTreeHeight和rightTreeHeight的较大值+1
        }
    
        public boolean isBalanced(TreeNode root) {
            if (root == null) {//根据例子3,当root为null时,返回true
                return true;
            }
            int leftTreeHeight = findHeightTree(root.left);//求root左子树的高度
            int rightTreeHeight = findHeightTree(root.right);//求root右子树的高度
            return Math.abs(leftTreeHeight - rightTreeHeight) <= 1/*左右高度差不超过1*/
                    && isBalanced(root.left)/*满足root的左数平衡*/
                    && isBalanced(root.right);//满足root的右数平衡
            //需要同时满足以上三个条件才返回true
        }
    }

### 2.运行结果 ###

![2faef8533c17428d893c1bb0d2852877.png][]

### 3.代码执行图示 ###

如求根节点3的递归过程

![e0043fae82f54cb8b43123cef3f40c1c.png][]

### 4.时间复杂度 ###

> **当遇到递归代码时,求其时间复杂度的时候,应该从解题思想上看,而不从代码本身上入手,因为每个节点都要求一次高度,有n个节点,而求高度findHeightTree方法的时间复杂度是O(n),所以时间复杂度为O(n^2)**

### 代码问题 ###

#### 1.存在重复计算 ####

#### 2.当不满足条件时,没有立即终止,递归仍在进行 ####

### 难度提升 (字节面试题) ###

#### (1) 面试官题问:能否以以O(n)的时间复杂度完成该问题? ####

#### (2)思路: 求高度的过程中,就判断是否平衡 ####

#### (3)代码如下 ####

class Solution {
        public boolean isBalanced(TreeNode root){
            return findHeightTree(root)>=0;
        }
        public int findHeightTree(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftTreeHeight = findHeightTree(root.left);
            int rightTreeHeight = findHeightTree(root.right);
            if (leftTreeHeight>=0&&rightTreeHeight>=0&&Math.abs(leftTreeHeight - rightTreeHeight) <= 1) {
                return Math.max(leftTreeHeight,rightTreeHeight)+1;
            }else {
                return -1;//说明此时已经不平衡,因为高度不可能为负数,所以返回-1来表示
            }
        }
    }

#### (4)运行结果 ####

![c64e8308bfd04577a23203939691010f.png][]

#### (5)代码执行图示 ####

![0b00dcabbc7a47538041906b21664a6a.png][]

#### (6)代码略微改动 ####

class Solution {
        public boolean isBalanced(TreeNode root){
            return findHeightTree(root)>=0;
        }
        public int findHeightTree(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftTreeHeight = findHeightTree(root.left);
            if (leftTreeHeight<0){
                return -1;
            }
            int rightTreeHeight = findHeightTree(root.right);
            if (rightTreeHeight<0){
                return -1;
            }
            if (Math.abs(leftTreeHeight - rightTreeHeight) <= 1) {
                return Math.max(leftTreeHeight,rightTreeHeight)+1;
            }else {
                return -1;//说明此时已经不平衡,因为高度不可能为负数,所以返回-1来表示
            }
        }
    }

#### (7)图解 ####

![2e096a30fd104122afdeca4bec934aad.png][]

## 完结撒花,宝子们动动你发财的小手给博主点个关注吧!!!爱你们(＾Ｕ＾)ノ~ＹＯ ##

[a666e9274c28441ab4924860211db197.jpeg]: https://img-blog.csdnimg.cn/a666e9274c28441ab4924860211db197.jpeg
[6b75e3e28f1443098a41f7d95e25e072.jpeg]: https://img-blog.csdnimg.cn/6b75e3e28f1443098a41f7d95e25e072.jpeg
[2faef8533c17428d893c1bb0d2852877.png]: https://img-blog.csdnimg.cn/2faef8533c17428d893c1bb0d2852877.png
[e0043fae82f54cb8b43123cef3f40c1c.png]: https://img-blog.csdnimg.cn/e0043fae82f54cb8b43123cef3f40c1c.png
[c64e8308bfd04577a23203939691010f.png]: https://img-blog.csdnimg.cn/c64e8308bfd04577a23203939691010f.png
[0b00dcabbc7a47538041906b21664a6a.png]: https://img-blog.csdnimg.cn/0b00dcabbc7a47538041906b21664a6a.png
[2e096a30fd104122afdeca4bec934aad.png]: https://img-blog.csdnimg.cn/2e096a30fd104122afdeca4bec934aad.png