本文共 1121 字，大约阅读时间需要 3 分钟。

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

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

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

示例 1：

输入：root = []

思路

-左右子树高度差的绝对值小于等于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;        }        int lh=getHigh(root.left);        int rh=getHigh(root.right);        return Math.abs(lh-rh)<=1&&isBalanced(root.left)&&isBalanced(root.right);    }    //求高度    public int getHigh(TreeNode root){
           if(root==null){
               return 0;        }        int lh=getHigh(root.left);        int rh=getHigh(root.right);        return Math.max(lh,rh)+1;    }}

复杂度

时间复杂度O(n log n)

空间复杂度O(n):树退化为链表递归深度n

转载地址：https://blog.csdn.net/qq_45630711/article/details/115435346 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！