判断是否为平衡二叉树（Java）

判断是否为平衡二叉树（Java） 判断是否为平衡二叉树

（牛客网—牛客题霸算法篇—NC62）

题目描述

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

思路

Java实现
这道题目其实和求二叉树的深度用到的方法是一样的，因为我们求二叉树的深度，其实就是求了左右子树的深度的最大值。

我们都知道如何判断一棵二叉树是不是平衡二叉树，就是它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

所以，这个时候我们只需要判断左右子树的深度之差有没有超过1，若超过了则不是平衡的，反之则为平衡二叉树。

代码实现

public class Solution {
    boolean isBalanced = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        TreeDepth(root);
        return isBalanced;
    }
public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        int l = TreeDepth(root.left);
        if(l == -1)  return -1;  // 提前返回
        int r = TreeDepth(root.right);
        if(r == -1)  return -1;  // 提前返回
        if(Math.abs(l-r) > 1){
            isBalanced = false;  // 不是平衡树
            return -1;  // 加一个标记-1，已经不可能是平衡树了
        }
        return Math.max(l,r)+1;
    }
}