题目主要信息:
- 判断给出的二叉树是否是平衡二叉树
- 需要判断任意一节点两边子树深度相差是否绝对值大于1,同时它的子树也符合平衡二叉树的规则
举一反三:
学习完本题的思路你可以解决如下题目:
方法一:自顶向下(推荐使用)
知识点:二叉树递归
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程,最重要的就是查看能不能讲原本的问题分解为更小的子问题,这是使用递归的关键。
而二叉树的递归,则是将某个节点的左子树、右子树看成一颗完整的树,那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题,因此可以自我调用函数不断进入子树。
思路:
平衡二叉树任意节点两边的子树深度相差绝对值不会超过1,且每个子树都满足这个条件,那我们可以对每个节点找到两边的深度以后:
int deep(TreeNode root){
if(root == null)
return 0;
int left = deep(root.left);
int right = deep(root.right);
//子树最大深度加上自己
return (left > right) ? left + 1 : right + 1;
}
判断是否两边相差绝对值超过1:
//左子树深度减去右子树相差绝对值大于1
if(left - right > 1 || left - right < -1)
return false;
然后因为每个子树都满足这个条件,我们还需要遍历二叉树每个节点当成一棵子树进行判断,而对于每个每个节点判断后,其子节点就是子问题,因此可以用递归。
IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
具体做法:
- step 1:第一个函数递归遍历二叉树所有节点。
- step 2:对于每个节点判断,调用第二个函数获取子树深度。
- step 3:第二个函数递归获取子树深度,只需要不断往子节点深度遍历,累加左右深度的较大值。
- step 4:根据深度判断该节点下的子树是否为平衡二叉树。
图示:
Java实现代码:
public class Solution {
//计算该子树深度函数
public int deep(TreeNode root){
//空节点深度为0
if(root == null)
return 0;
//递归算左右子树的深度
int left = deep(root.left);
int right = deep(root.right);
//子树最大深度加上自己
return (left > right) ? left + 1 : right + 1;
}
public boolean IsBalanced_Solution(TreeNode root) {
//空树为平衡二叉树
if (root == null)
return true;
int left = deep(root.left);
int right = deep(root.right);
//左子树深度减去右子树相差绝对值大于1
if(left - right > 1 || left - right < -1)
return false;
//同时,左右子树还必须是平衡的
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
}
C++实现代码:
class Solution {
public:
//计算该子树深度函数
int deep(TreeNode* root){
//空节点深度为0
if(root == NULL)
return 0;
//递归算左右子树的深度
int left = deep(root->left);
int right = deep(root->right);
//子树最大深度加上自己
return (left > right) ? left + 1 : right + 1;
}
bool IsBalanced_Solution(TreeNode* pRoot) {
//空树为平衡二叉树
if(pRoot == NULL)
return true;
int left = deep(pRoot->left);
int right = deep(pRoot->right);
//左子树深度减去右子树相差绝对值大于1
if(left - right > 1 || left - right < -1){
return false;
}
//同时,左右子树还必须是平衡的
return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
}
};
Python实现代码
class Solution:
#计算该子树深度函数
def deep(self, root: TreeNode):
if not root:
return 0
# 递归算左右子树的深度
left = self.deep(root.left)
right = self.deep(root.right)
# 子树最大深度加上自己
return left + 1 if left > right else right + 1
def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
# 空树为平衡二叉树
if not pRoot:
return True
left = self.deep(pRoot.left)
right = self.deep(pRoot.right)
# 左子树深度减去右子树相差绝对值大于1
if left - right > 1 or left - right < -1:
return False
# 同时,左右子树还必须是平衡的
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
复杂度分析:
- 时间复杂度:,其中为二叉树的节点数,第一个递归遍历二叉树所有节点,第二个递归查找深度最坏情况下(二叉树退化为链表)需要遍历二叉树所有节点
- 空间复杂度:,递归栈最大深度为
方法二:自底向上(扩展思路)
思路:
上述一个函数算深度,一个函数遍历所有节点的方法,用了两个递归,做了很多不必要的运算,这就是自顶向下的弊端。那我们可以考虑自底向上,因为其实我们判断某个节点是否符合平衡二叉树特性的时候,需要的不是左右子树的完整深度,而是深度差,只要深度差绝对值不超过1,就可以满足。因此在底部计算深度的同时,判断该子树是否为平衡二叉树,将是或否与深度差一起往上传就行。
具体做法:
- step 1:先判断空树,直接为平衡二叉树。
- step 2:递归进行边计算深度边判断是否平衡二叉树。
- step 3:递归计算当前节点左右子树的深度差,然后比较深度差是否符合平衡二叉树。
- step 4:每次递归都将深度结果往上传,遇到不符合平衡二叉树的,返回-1,而深度差我们取绝对值保证返回正数,因此最后的负数一定就是 不满足条件,这样就能做到边判断边计算深度了。
图示:
Java实现代码:
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
//空树也是平衡二叉树
if(root == null)
return true;
return getdepth(root) != -1;
}
public int getdepth(TreeNode root) {
if(root == null)
return 0;
//递归计算当前root左右子树的深度差
int left = getdepth(root.left);
//当前节点左子树不平衡,则该树不平衡
if(left < 0)
return -1;
int right = getdepth(root.right);
//当前节点右子树不平衡,则该树不平衡
if(right < 0)
return -1;
//计算深度差
return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
}
C++实现代码:
class Solution {
public:
//计算该子树深度
bool judge(TreeNode* root, int& depth){
//空节点深度为0
if(root == NULL){
depth = 0;
return true;
}
//准备计算左右子树的深度
int left = 0;
int right = 0;
if(judge(root->left, left) == false || judge(root->right, right) == false)
return false;
//左子树深度减去右子树相差绝对值大于1
if(left - right > 1 || left - right < -1)
return false;
//子树最大深度加上自己
depth = (left > right) ? left + 1 : right + 1;
//该节点满足要求
return true;
}
bool IsBalanced_Solution(TreeNode* pRoot) {
int depth = 0;
return judge(pRoot, depth);
}
};
Python实现代码
class Solution:
# 计算该子树深度
def getdepth(self, root: TreeNode) -> int:
if not root: # 空节点深度为0
return 0
# 递归计算当前root左右子树的深度差
left = self.getdepth(root.left)
# 当前节点左子树不平衡,则该树不平衡
if left < 0:
return -1
right = self.getdepth(root.right)
# 当前节点右子树不平衡,则该树不平衡
if right < 0:
return -1
return -1 if abs(left-right) > 1 else 1 + max([left, right])
def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
if not pRoot:
return True
return self.getdepth(pRoot) != -1
复杂度分析:
- 时间复杂度:,其中为树的节点数,一次递归遍历二叉树所有节点
- 空间复杂度:,最坏情况下递归栈的深度为