110、平衡二叉树

平衡二叉树

题目描述

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

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

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

​ 3

/
9 20
/
15 7
返回 true 。

思路分析

思路一：从根节点判断左右子树高度是否相差超过1。从顶点到叶节点遍历存在重复计算。代码如下：

public boolean isBalanced(TreeNode root) {
    if (root==null)return true;
    int left=getDepth(root.left);
    int right=getDepth(root.right);
    if (Math.abs(left-right)>1)return false;
    return isBalanced(root.left)&&isBalanced(root.right);
}
public int getDepth(TreeNode root){
    return root==null?0:Math.max(getDepth(root.left),getDepth(root.right))+1;
}

思路二：在求二叉树高度的时候同时判断二叉树是否平衡，避免了重复计算。代码如下：

public boolean isBalanced(TreeNode root) {
    return getMaxDepth(root)!=-1;
}
public int getMaxDepth(TreeNode root){
    if (root==null)return 0;
    int left=getMaxDepth(root.left);
    if (left==-1)return -1;
    int right=getMaxDepth(root.right);
    if(right==-1)return -1;
    if (Math.abs(left-right)>1){
        return -1;
    }else {
        return Math.max(left,right)+1;
    }
}