AlgoPressAppearance
0110-平衡二叉树
https://leetcode.cn/problems/balanced-binary-tree
给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1： 
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
提示：
树中的节点数在范围 [0, 5000] 内
-10^4 <= Node.val <= 10^4
思路1：自顶而下递归
根据定义增加函数计算两边树的高度，然后计算是否相差小于1用来判断。
注意平衡二叉树的子节点也必须是平衡二叉树
参考代码
csharp
public class Solution {
private 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;
}
public bool IsBalanced(TreeNode root) {
if(root == null){
return true;
}
int leftHeight = Height(root.left);
int rightHeight = Height(root.right);
return Math.Abs(leftHeight-rightHeight) <= 1 && IsBalanced(root.left) && IsBalanced(root.right);
}
}
思路2：自底而上递归
在思路1中，重复计算了很多此树的高度，其实我们如果我们发现子树不是平衡之后，就可以直接返回不平衡，从而不需要重复计算。 我们用高度 -1 表示不平衡
csharp
public class Solution{
private int Height(TreeNode root){
if(root == null){
return 0;
}
int leftHeight = Height(root.left);
if(leftHeight == -1){
return -1;
}
int rightHeight = Height(root.right);
if(rightHeight == -1 || Math.Abs(leftHeight - rightHeight) > 1){
return -1;
}
return Math.Max(leftHeight,rightHeight)+1;
}
public bool IsBalanced(TreeNode root){
return Height(root) != -1;
}
}
复习:20220512
csharp
public class Solution {
private int depth(TreeNode root){
if(root == null){
return 0;
}
int left = depth(root.left);
int right = depth(root.right);
if(left == -1 || right == -1 || Math.Abs(left-right) > 1){
return -1;
}
return Math.Max(left,right)+1;
}
public bool IsBalanced(TreeNode root) {
return depth(root) != -1;
}
}