题目
输出一棵节点数为 n 二叉树,判断该二叉树是否是均衡二叉树。
在这里,咱们只须要思考其平衡性,不须要思考其是不是排序二叉树
均衡二叉树(Balanced Binary Tree),具备以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1,并且左右两个子树都是一棵均衡二叉树。
样例解释:
样例二叉树如图,为一颗均衡二叉树
注:咱们约定空树是均衡二叉树。
数据范畴:n≤100, 树上节点的 val 值满足 0≤n≤1000
要求:空间复杂度 O(1),工夫复杂度 O(n)
参数阐明:二叉树类,二叉树序列化是通过按层遍历,# 代表这这个节点为空节点,举个例子:
1
/ \
2 3
/
4
以上二叉树会被序列化为 {1,2,3,#,#,4}
示例 1
输出:{1,2,3,4,5,6,7}
返回值:true
示例 2
输出:{}
返回值:true
思路
- 用递归的办法计算每个节点的深度(节点深度 = 左右子树深度最大值 +1)。
- 判断节点左右子树深度的差值是否大于 1,大于 1 则不是均衡的。
- 同时递归判断左右子树也得是均衡的。
- 这个算法还有一个优化的思路是:递归的函数判断是否均衡的同时返回节点的深度(解法略)。
解答代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
#include <algorithm>
class Solution {
public:
/**
* @param pRoot TreeNode 类
* @return bool 布尔型
*/
bool IsBalanced_Solution(TreeNode* pRoot) {
// write code here
if (pRoot == nullptr) {return true;}
auto left_depth = Depth(pRoot->left);
auto right_depth = Depth(pRoot->right);
// 左右子树深度相差大于 1
if (left_depth - right_depth > 1 || right_depth - left_depth > 1) {return false;}
// 同时左右子树也都得是均衡二叉树
return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
}
int Depth(TreeNode* pRoot) {if (pRoot == nullptr) {return 0;}
auto left_depth = Depth(pRoot->left);
auto right_depth = Depth(pRoot->right);
// 根的深度是子树最大深度 +1
return max(left_depth+1, right_depth+1);
}
};