剑指offer-39、均衡⼆叉树
题⽬形貌输⼊⼀棵节点数为 n ⼆叉树，判断该⼆叉树是否是均衡⼆叉树。
在这⾥，我们只须要思量其均衡性，不须要思量其是不是排序⼆叉树
均衡⼆叉树（ Balanced Binary Tree ），具有以下性子：它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不凌驾 1 ，而且左右两个⼦树都是⼀棵均衡⼆叉树。
样例表明：
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9zZXZlbjk3LWJsb2cub3NzLWNuLWhhbmd6aG91LmFsaXl1bmNzLmNvbS9pbWdzLzIwMjUwNTI1MTA1NjM0MS5wbmc=
思绪及解答
自顶向下递归（根本解法）
均衡树意味着我们须要对⽐任安在同⼀个根下的左右⼦树的⾼度差，还记得之前我们盘算树的⾼度么，使⽤递归⽅式来办理，实在这道题与算⾼度差不多，只是两边⾼度须要算出⼀个差值。
算法的重要头脑：
[*]不绝对⽐每两个节点的左右⼦树的最⼤⾼度差，留意取差的绝对值，须要⼩于便是1
[*]对⽐完左右⼦树之后，须要递归左⼦树以及右⼦树进⾏分别判断，都满⾜才是均衡树
public class Solution79 {
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) return true;
// 当前左右⼦树是否平衡以及左右⼦树分别是否平衡
return Math.abs(depth(root.left) - depth(root.right)) <= 1 &&
IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
// 递归获取深度
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}
[*]时间复杂度 O(n) ：每个节点盘算⼀次
[*]空间复杂度 O(n) ：递归须要使⽤额外堆栈空间
笔试口试时，发起首选这个方式，服从最优，代码简便
封装信息法（面向对象思绪）
通过自界说类同时返回高度宁静衡信息，代码结构更清楚。
public class Solution79 {
public boolean IsBalanced_Solution(TreeNode root) {
// 空树
if (root == null) {
return true;
}
return getHeight(root) != -1;
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;//空节点高度为0
}
// 左⼦树的⾼度
int left = getHeight(root.left);
if (left < 0) {
return -1;//左子树不平衡，直接返回
}
// 右⼦树的⾼度
int right = getHeight(root.right);
if (right < 0) {
return -1;//右子树不平衡，直接返回
}
// 检查当前节点是否平衡
return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]