110. 平衡二叉树

1、概要

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

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

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

和二叉树最大深度有很大区别

leetcode中强调的深度和高度很明显是按照节点来计算的

因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

既然要求比较高度，必然是要后序遍历。

虽是返回boolean，但是还是用-1来标记不符合，所以递归函数返回高度，以便计算差值是否大于1。使用abs求绝对值。

2、思路

递归

• 递归函数的参数和返回值

当前传入节点，返回以当前传入节点为根节点的树的高度

private int reCurSion(TreeNode root)

• 终止条件

依然是遇到空节点了为终止，返回0

if(root == null){return 0;}

• 单层逻辑

分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了

 		int leftHeight = reCurSion(root.left);
		if(leftHeight == -1){
            return -1;
        }
        int rightHeight = reCurSion(root.right);
        if(rightHeight == -1){
            return -1;
        }
        //左右子树高度差大于1，返回-1，不平衡
        if(Math.abs(leftHeight-rightHeight) > 1){
            return -1;
        }
		//Math.abs() 是 Java 中的一个函数，用于计算一个数的绝对值。这个函数接受一个参数，可以是整数、浮点数或长整型，并返回该数的绝对值。
		//Math.abs() 函数可以用于各种数值类型，包括 int、long、float 和 double。

        return Math.max(leftHeight,rightHeight) +1;

迭代

此题用迭代法，其实效率很低，因为没有很好的模拟回溯的过程，所以迭代法有很多重复的计算。

虽然理论上所有的递归都可以用迭代来实现，但是有的场景难度可能比较大。

3、代码

class Solution {
    public boolean isBalanced(TreeNode root) {
        return reCurSion(root) != -1;
    }

    private int reCurSion(TreeNode root){
        if(root == null){return 0;}
        int leftHeight = reCurSion(root.left);
        if(leftHeight == -1){
            return -1;
        }
        int rightHeight = reCurSion(root.right);
        if(rightHeight == -1){
            return -1;
        }
        //左右子树高度差大于1，返回-1，不平衡
        if(Math.abs(leftHeight-rightHeight) > 1){
            return -1;
        }

        return Math.max(leftHeight,rightHeight) +1;

    }

    
}