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;
}
}