24_110. 平衡二叉树
题目描述：
解题思路：
一、自顶向下的递归
这个类似于二叉树的前序遍历，首先判断当前节点是否符合平衡二叉树（即其左右字数的高度差是否不超过1），如果不超过1，再分别递归地遍历左右子节点，并判断左右字数是否平衡。
这也是我能想的递归了，但是当考虑其复杂度的时候，由于是自顶向下，对于同一个节点，求其高度这个过程会重复调用，越靠近二叉树底层，调用的次数越多，就导致了时间复杂度的大大提升。
二、自底向上的递归
该做法类似于后序遍历，对于当前节点，先递归的判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一颗子树是平衡的，则返回其高度（高度一定是非负数），否则返回-1。如果存在一颗子树不平衡，则整个二叉树一定不平衡。
时间复杂度从O(n2)--->O(n)，空间复杂度都是O(n)
自顶向下
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
public int height(TreeNode root){
if(root == null){
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.max(leftHeight,rightHeight) + 1;
}
}
自底向上
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0 ;
}
public int height(TreeNode root){
if(root == null){
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1){
return -1;
}
return Math.max(leftHeight , rightHeight) + 1;
}
}