描述
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
注：我们约定空树是平衡二叉树。
示例
输入：{1,2,3,4,5,6,7}
返回值：true引言
有关树的题目很多都可以使用递归解决，但需要注意栈溢出的问题。
递归只要关心递归方法能实现的功能，而无需陷入其中去理解每一层递归的细节，否则只会自行提高题目难度
知识点：二叉树，递归
难度：二星
题解
解题思路
一看到树的题目就要想到使用递归解决问题，而且有时候可以通过使用递归、遍历等框架解题。
本题可以使用自顶向下的暴力法来遍历整棵树，时间复杂度相对较高
也可以使用自底向上的递归，最关键就是要阻断递归，递归到一定情况要结束当前节点递归，降低时间复杂度
方法一：暴力法：自顶向下
算法流程：
- 通过比较每个节点的左右子树的最大高度差, 来判断此子树是否是二叉平衡树。
- 若树的所有子树都平衡时，该树才是平衡二叉树。
Java 版本代码如下：
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) return true;
// 高度差不能大于1，并且左右子树也是同样高度差要小于等于1
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;
}
}
Python 版本代码如下：
class Solution:
def IsBalanced_Solution(self, root: TreeNode) -> bool:
if not root: return True
# 高度差不能大于1，并且左右子树也是同样高度差要小于等于1
return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
self.IsBalanced_Solution(root.left) and self.IsBalanced_Solution(root.right)
def depth(self, root):
if not root: return 0
# 左右子树中高度较大的作为当前节点高度
return max(self.depth(root.left), self.depth(root.right)) + 1复杂度分析：
时间复杂度 O(Nlog2N)：最差情况下，需要遍历树所有节点判断是否平衡，需要O(N)。判断每个节点最大高度需要递归左右子树，需要占用 O(log2N)，所以总共占用O(Nlog2N)
空间复杂度O(N)：最差情况下（树退化为链表时），递归需要使用O(N) 的栈空间。
方法二：自底向上递归
图解
算法流程：
判断空树，题目要求空树也是平衡二叉树
递归计算当前root左右子树的高度差
注意：递归过程中有左/右子树不平衡,则该树不平衡，相当于可行性剪枝，没必要遍历所有节点
递归到底后，自底向顶，每次+1，不断计算高度，直到递归到某个节点使得左右子树高度差大于1，则返回-1表示不平衡
左右子树中高度较高的, 作为当前节点的高度, 用于向上递归判断是否平衡
递归终止条件：
- root 为 null
- 左右子树高度差大于1，即左右子树其中一个节点返回-1，则递归终止，阻断递归，表示不是平衡二叉树
递归方法的功能：获取当前节点的树的高度
Java 版本代码如下：
public class Solution {
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;
}
// 递归计算当前root左右子树的高度差
int left = getHeight(root.left);
// 当前节点左子树不平衡,则该树不平衡，相当于可行性剪枝，没必要遍历所有节点
if(left < 0) {
return -1;
}
int right = getHeight(root.right);
if(right < 0) {
return -1;
}
// 自底向顶，每次+1，不断计算高度，直到递归到某个节点使得左右子树高度差大于1，则返回-1表示不平衡
// 左右子树中高度较高的, 作为当前节点的高度, 用于向上递归判断是否平衡
return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
} Python 版本代码如下：
class Solution:
# 计算root节点的高度
def high(self,root):
if root == None:
return 0
left = self.high(root.left)
right = self.high(root.right)
ans = max(left,right)+1
return ans
def IsBalanced_Solution(self, pRoot):
if pRoot == None:
return True
# 提前阻断，可行性剪枝
if not self.IsBalanced_Solution(pRoot.left):
return False
if not self.IsBalanced_Solution(pRoot.right):
return False
highleft = self.high(pRoot.left)
highright = self.high(pRoot.right)
isbalance = highleft - highright
# 当前节点高度差
if isbalance > 1 or isbalance < -1:
return False
return True
# write code here 复杂度分析：
时间复杂度O(N)：递归最差情况下（树退化为链表时），需要使用 O(N) 的栈空间。
空间复杂度O(N)：递归需要使用额外的树节点数量的堆栈空间
京公网安备 11010502036488号