平衡二叉树（剑指offer）

佚名 6年前 (2019-04-12) 随笔 979人围观抢沙发百度已收录

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。 方法一：通过求树的高度 高度差大于1，就不是平衡数。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null) return true;
        if(Math.abs(getHeigh(root.left)-getHeigh(root.right))>1)
            return false;
        return IsBalanced_Solution(root.right)&&IsBalanced_Solution(root.right);
    }
    public int getHeigh(TreeNode root){
        if(root==null)  return 0;
        int leftRoot=getHeigh(root.left);
        int rightRoot=getHeigh(root.right);
        return Math.max(leftRoot,rightRoot)+1;
    }
}

方法二：剪枝法

方法一开销太大，需要遍历每一个结点，在方法一上改进得到第二个方法。从叶子结点开始遍历，遇到不是平衡树就返回。剩下的不用遍历了。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return getHeigh(root)!=-1;
    }
    public int getHeigh(TreeNode root){
        if(root==null)  return 0;
        int leftRoot=getHeigh(root.left);
        if (leftRoot==-1) return -1;
        int rightRoot=getHeigh(root.right);
        if (rightRoot==-1) return -1;
        return Math.abs(leftRoot-rightRoot)>1?-1:Math.max(leftRoot,rightRoot)+1;
    }
}