判断二叉树是否是平衡二叉树,b+树是不是平衡二叉树
BM36判断是否是平衡二叉树。
知识点树
描述一棵有n个节点的二叉树，判断该二叉树是否为平衡二叉树。在这里，我们只需要考虑它的平衡性，而不需要考虑它是否是一棵平衡二叉树。它具有以下性质：它是一棵空树或其左右子树高度差的绝对值不超过1，左右子树都是平衡二叉树。
示例：样本二叉树如图所示，是一棵平衡二叉树。
注意：我们同意空树是平衡二叉树。
数据范围：树上节点的val值满足要求：空间复杂度和时间复杂度。
描述：输入二叉树的根节点。
返回值描述：输出一个布尔值。
示例1输入：
{1，2，3，4，5，6，7}复制返回值：
准确的副本
2示例输入：
{}复制返回值：
真解方法一：自顶向下递归实现判断一个数是否是平衡二叉树。平衡二叉树是左子树的高度和右子树的高度之差的绝对值小于或等于1。类似地，左边的子树是平衡二叉树，右边的子树是平衡二叉树。
根据定义，如果我们能求出以每个节点为根的树的高度，然后根据左右子树高度差的绝对值小于等于1来判定以每个节点为根的树是否满足定义。
#包含位/标准数据。h
//https://www . now coder . com/practice/8b3b 95850 EDB 4115918 ECB df 1 B4 d 222？tpId=295 tags=title=难度=0判断状态=0 rp=0来源URL=/考试/oj
定义树结构
{
int val
struct TreeNode * left
struct TreeNode * right
TreeNode(int x) : val(x)，left(nullptr)，right(nullptr) {}
};
int height(TreeNode *node)
{
if (node==nullptr)
{
返回0；
}
return STD:max(height(node-left)，height(node-right))1；
}
bool is balanced _ Solution(TreeNode * pRoot)
{
if (pRoot==nullptr)
{
返回true
}
auto left _ height=height(pRoot-left)；
auto right _ height=height(pRoot-right)；
return STD:ABS(left _ height-right _ height)=1 is balanced _ Solution(pRoot-left)is balanced _ Solution(pRoot-right)；
}方法二：自底向上递归实现
在第一种方法中，我们从上到下计算根节点上每个节点的高度。因为递归，实际上有很多重复计算。如果改成自下而上的方式，可以减少很多不必要的计算。因此，我们可以通过后续遍历的方式对上述方法进行优化。在求高度的过程中，如果一个子节点不满足平衡二叉树，我们可以提前判断整个二叉树不是平衡二叉树，然后我们可以提前退出递归。代码如下：
//-1表示不是平衡二叉树，大于等于0表示二叉树的高度
int深度(TreeNode *root)
{
if (root==nullptr)
{
返回0；
}
int left _ height=depth(root-left)；
If (left_height==-1)//如果左子树不满足平衡二叉树的条件，则提前退出。
{
return-1；
}
int right _ height=depth(root-right)；
If (right_height==-1)//早点退出
{
return-1；
}
int ABS=STD:ABS(left _ height-right _ height)；
如果(abs 1)
{
return-1；//如果左右子树的高度差大于1，则返回-1。
}
return std:max(left_height，right _ height)1；//返回当前节点的高度
}
bool is balanced _ Solution _ 2(TreeNode * pRoot)
{
返回深度(pRoot)！=-1;
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。