LeetCode_二叉平衡树_简单_110.平衡二叉树

缺乏、安全感 2023-10-07 20:24 12阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例 1：**  
![在这里插入图片描述][c69eeebc480640d080fc695e4b4e5787.png]  
输入：root = \[3,9,20,null,null,15,7\]  
输出：true

**示例 2：**  
![在这里插入图片描述][2b79d5bd2cbb4116af5abb46a3816ca8.png]  
输入：root = \[1,2,2,3,3,null,null,4,4\]  
输出：false

**示例 3：**  
输入：root = \[\]  
输出：true

**提示：**  
树中的节点数在范围 \[0, 5000\] 内  
\-104 <= Node.val <= 104

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/balanced-binary-tree

## 2.思路 ##

（1）二叉平衡树判定  
该二叉树的根节点为 root，那么该二叉树为平衡二叉树的充要条件是：  
① 根节点的左右两个子树的高度差的绝对值不超过 1；  
② 根节点的左子树为平衡二叉树；  
③ 根节点的右子树也为平衡二叉树；

## 3.代码实现（Java） ##

//思路1————二叉平衡树判定
    /**
     * 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) {
        
            if (root == null) {
        
                return true;
            } else {
        
            	/*
            		该二叉树的根节点为 root，那么该二叉树为平衡二叉树的充要条件是：
    				(1) 根节点的左右两个子树的高度差的绝对值不超过 1：Math.abs(height(root.left) - height(root.right)) <= 1
    				(2) 根节点的左子树为平衡二叉树：isBalanced(root.left) == true
    				(3) 根节点的右子树为平衡二叉树：isBalanced(root.right) == true
    			*/
                return Math.abs(height(root.left) - height(root.right)) <= 1
                       && isBalanced(root.left) && isBalanced(root.right);
            }
        }
    	
    	//返回以 root 为根节点的树的高度
        public int height(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            } else {
        
                return Math.max(height(root.left), height(root.right)) + 1;
            }
        }
    }

[c69eeebc480640d080fc695e4b4e5787.png]: https://img-blog.csdnimg.cn/c69eeebc480640d080fc695e4b4e5787.png
[2b79d5bd2cbb4116af5abb46a3816ca8.png]: https://img-blog.csdnimg.cn/2b79d5bd2cbb4116af5abb46a3816ca8.png