AlgoPressAppearance
55-II-平衡二叉树
题目描述
https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
限制：
0 <= 树的结点个数 <= 10000
注意：本题与主站 110 题相同：https://leetcode.cn/problems/balanced-binary-tree/
思路分析
基本思路： 找出两个子节点的深度，相减比较大小是否超过1
实现代码
注意：最简单的考虑可能是 IsBalanced 函数直接判断 Math.Abs(leftDepth-rightDepth) <= 1 就可以了。 但实际上如果子节点左右不平衡，则答案就不正确了，如下面测试用例
[1,2,2,3,null,null,3,4,null,null,4]
1
/\
2 2
/ \
3 3
/ \
4 4
1 左右平衡，但是2左右不平衡，所以要用 dfs 遍历子节点
csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private bool isBalanced = true;
//求解最大深度
private int maxDepth(TreeNode cur){
if(cur == null){return 0;}
int leftDepth = maxDepth(cur.left);
int rightDepth = maxDepth(cur.right);
return Math.Max(leftDepth,rightDepth)+1;
}
private void dfs(TreeNode cur){
if(cur == null){return ;}
int leftDepth = maxDepth(cur.left);
int rightDepth = maxDepth(cur.right);
if(Math.Abs(leftDepth - rightDepth) > 1){
isBalanced = false;
return;
}
//检测子节点
dfs(cur.left);
dfs(cur.right);
}
public bool IsBalanced(TreeNode root) {
dfs(root);
return isBalanced;
}
}
参考代码2：考虑了左右平衡
csharp
public class Solution{
private int maxDepth(TreeNode cur){
if(cur == null){
return 0;
}
int leftDepth = maxDepth(cur.left);
int rightDepth = maxDepth(cur.right);
return Math.Max(leftDepth,rightDepth) + 1;
}
public bool IsBalanced(TreeNode root){
if(root == null){
return true;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.Abs(leftDepth - rightDepth) <= 1 && IsBalanced(root.left) && IsBalanced(root.right);
}
}
参考代码3：减少 IsBalanced 遍历
因为 maxDepth 求取深度的时候，对每个节点遍历了一次 然后 IsBalanced 判断左右是否平衡又对节点做了一次遍历。 这里我们在求 height 的时候，先直接判断左右子树是否平衡，如果不平衡，则直接返回 -1 ，因为子不平衡，那么上面节点也都不平衡。 所以父节点直接判断子节点高度是否是-1，如果是-1，则直接返回不再递归判断
csharp
public class Solution{
private int height(TreeNode cur){
if(cur == null){
return 0;
}
int left = height(cur.left);
int right = height(cur.right);
if(left == -1 || right == -1 || Math.Abs(left - right) > 1){
return -1;
}
return Math.Max(left,right)+1;
}
public bool IsBalanced(TreeNode root){
if(root == null){
return true;
}
int left = height(root.left);
int right = height(root.right);
if(left == -1 || right == -1 || Math.Abs(left - right) > 1){
return false;
}
return true;
}
}