【浅刷Java数据结构】LeetCode 110 平衡二叉树

链接: LeetCode 110 平衡二叉树

解法1：时间复杂度为O(n^2)

思路：某根节点点的左右子树都是平衡二叉树，并且自己的左右子树的最大高度差小于1，即为平衡二叉树

class Solution {
    public int maxDepth(TreeNode root) {//求以某个结点为根节点的深度
        if(root==null){
            return 0;
        }
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return left>right?left+1:right+1;
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftH = maxDepth(root.left);
        int rightH = maxDepth(root.right);
        return Math.abs(leftH-rightH)<=1&&
        isBalanced(root.left)&&
        isBalanced(root.right);
    }
}

解法2：时间复杂度为O(n)

在求高度的时候就进行检查，当其不满足平衡二叉树时，就返回一个负数，单出现一个负数时，说明这棵二叉树就已经不平衡了。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        if(left>=0 && right>=0 && Math.abs(left-right)<=1){
            return Math.max(left,right)+1;
        }else{
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return maxDepth(root)>=0;
    }
}