( “树” 之 DFS) 110. 平衡二叉树 ——【Leetcode每日一题】

矫情吗；* 2024-03-23 11:01 78阅读 0赞

### 110. 平衡二叉树 ###

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

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

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

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

![在这里插入图片描述][94094a0981004a57865af4f49c5514d7.png]

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

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

![在这里插入图片描述][f8887c113a27402c82681fdca69f73f9.png]

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

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

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

**提示：**

*  树中的节点数在范围 \[0, 5000\] 内
 *   − 1 0 4 < = N o d e . v a l < = 1 0 4 -10^4 <= Node.val <= 10^4 −104<=Node.val<=104

#### 思路：自底向上的递归 ####

自底向上递归的做法类似于**后序遍历**:

*  对于当前遍历到的节点，先递归地判断其左右子树是否平衡;
 *  再判断以当前节点为根的子树是否平衡。如果存在一棵子树不平衡，则整个二叉树一定不平衡, 则返回。
 *  如果一棵子树是平衡的，则返回其高度（取左右子树最大值）;

#### 代码：(Java、C++) ####

**Java**

/**
     * 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 {
        
        private boolean result = true;
        public boolean isBalanced(TreeNode root) {
        
            height(root);
            return result;
        }
        public int height(TreeNode root){
        
            if(root == null) return 0;
            int left = height(root.left);
            int right = height(root.right);
            if(Math.abs(left - right) > 1){
        
                result = false;
                return 0;
            }
            return 1 + Math.max(left, right);
        }
    }

**C++**

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        bool result = true;
        bool isBalanced(TreeNode* root) {
        
            height(root);
            return result;
        }
        int height(TreeNode* root){
        
            if(root == NULL) return 0;
            int left = height(root->left);
            int right = height(root->right);
            if(abs(left - right) > 1){
        
                result = false;
                return 0;
            }
            return 1 + max(left, right);
        }
    };

##### 运行结果： #####

![在这里插入图片描述][0617e652abab48d887e093d535f95106.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是  O ( n ) O(n) O(n)。
 *  **空间复杂度**： O ( n ) O(n) O(n)，其中 `n` 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 `n`。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[94094a0981004a57865af4f49c5514d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/8d7111942a5e48bcbf1bd6887246db4f.png
[f8887c113a27402c82681fdca69f73f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/e3e0ceffa910406a8c99ea680294bcb0.png
[0617e652abab48d887e093d535f95106.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/4dd632e0a21f4f798c8c7d619f54fe70.png
[Link 1]: https://leetcode.cn/problems/balanced-binary-tree/description/
[leetCode]: http://t.csdn.cn/kQLJO