首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何确定二叉树是否平衡?

要确定一个二叉树是否平衡,可以使用以下方法:

  1. 计算二叉树的高度:首先,需要计算二叉树的高度。可以使用递归方法来实现这个功能。对于一个空树,其高度为0;对于一个非空树,其高度为左子树和右子树中较高的那个加1。
  2. 检查左右子树的高度差:在计算出二叉树的高度后,可以检查左右子树的高度差。如果高度差小于等于1,则说明二叉树是平衡的;否则,二叉树就是不平衡的。

以下是一个简单的Python代码实现:

代码语言:python
代码运行次数:0
复制
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height(root):
    if not root:
        return 0
    return max(height(root.left), height(root.right)) + 1

def is_balanced(root):
    if not root:
        return True
    left_height = height(root.left)
    right_height = height(root.right)
    if abs(left_height - right_height) > 1:
        return False
    return is_balanced(root.left) and is_balanced(root.right)

在这个代码中,我们定义了一个TreeNode类来表示二叉树的节点,并实现了heightis_balanced两个函数。height函数用于计算二叉树的高度,而is_balanced函数则用于检查二叉树是否平衡。

需要注意的是,这个算法的时间复杂度为O(n^2),因为我们需要计算每个节点的高度。如果需要更高效的算法,可以考虑使用后序遍历的方式来计算二叉树的高度,并在遍历过程中检查每个节点的左右子树的高度差。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

判断二叉树是否平衡二叉树

题目: 输入一颗二叉树的根节点,判断该树是不是平衡二叉树。 1.平衡二叉树 定义:一棵空树或它的任意节点的左右两个子树的高度差的绝对值均不超过1。...下面就是一颗平衡二叉树: image.png 2.解法一 解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过...1,按照定义,它就是一颗平衡二叉树。...,就可以方便的判断出二叉树平衡二叉树,思路简单,代码简洁。...例如在上面的函数输入isBalanced()函数中输入如下二叉树: image.png 我们首先判断根节点1是不是平衡的,此时我们需要调用treeDepth()函数求根节点左子树的高度,需要遍历节点

1.8K20

平衡二叉树

因此引入了平衡二叉树(AVL树)——节点左右子树的高度差的绝对值不超过1....当我们把一个节点插入到平衡二叉树中的时候,就有可能打破原有的平衡,这时候我们就需要调整该树,使它继续保持平衡二叉树的特性。...插入的情况 插入一个节点,只会影响它父亲的平衡因子,而父亲节点平衡因子的变化也会影响它的父亲节点 如果插入的是父节点的左边,父亲节点的平衡因子减1 如果插入的是父节点的右边,父亲节点的平衡因子加1...什么情况下才会使插入节点所在的路径上节点的平衡因子不在发生变化呢?...当按上面的规则执行之后,节点的平衡因子为0,说明左右子树都平衡了,就不用继续往上进行调整了,或者已经调整到根节点了,就不用调整了。

16110

平衡二叉树

平衡二叉树 给定一个二叉树,判断它是否是高度平衡二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。...示例 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true。...dfs(root); return target; }; 思路 定义一个深度递归遍历的函数,在一个节点中获取树的左右子树的高度,也就是定义获取树的高度的函数,在获取左右子树的高度时比较左右子树是否平衡即可...,首先定义目标变量target,之后定义深度递归遍历dfs函数,在函数中判断节点不存在则返回0,接下来是一部分剪枝,如果已经找到了不平衡的位置那么就没有必要继续向下遍历,之后定义l为左子树的高度,r为右子树的高度...,之后进行比较如果做右子树的高度差大于1则认为其不是平衡二叉树,赋值target为false,之后返回做右子树中高的子树的高度+1,执行dfs深度递归遍历,完成后返回target即可。

20620

平衡二叉树

定义 最小不平衡子树 基本思想 构造平衡二叉树 二叉平衡树调整的四种类型 总结 完整代码 #include using namespace std; //平衡二叉树...因此下面我们要对oldRoot下面的左子树newRoot的bf进行判断,看是LL还是LR的情况 switch (newRoot->bf) { case LH://LL的情况---右旋处理,处理完后,最小不平衡子树变为平衡二叉树...因此下面我们要对oldRoot下面的左子树newRoot的bf进行判断,看是LL还是LR的情况 switch (newRoot->bf) { case LH://LL的情况---右旋处理,处理完后,最小不平衡子树变为平衡二叉树...因此下面我们要对oldRoot下面的左子树newRoot的bf进行判断,看是LL还是LR的情况 switch (newRoot->bf) { case LH://LL的情况---右旋处理,处理完后,最小不平衡子树变为平衡二叉树...->lchild;//去左子树里面查找 } else { ptr = ptr->rchild; } } return false; } //删除节点的函数----删除时要注意是否破坏了平衡

22420

平衡二叉树

概念 平衡因子:每个结点的平衡因子就是左右子树的高度之差,即可用如下公式表示:BF(T) = Hl-Hr 平衡二叉树平衡二叉树可能是空树,也有可能是左右子树高度之差小于等于1的树,即平衡因子的绝对值小于等于...如下图所示,不平衡的原因是因为A的左孩子B的左子树插入了新结点而导致了A的不平衡,那么就要利用LL旋转来调整不平衡结点A,由于平衡二叉树一定是二叉搜索树,设定插入结点为C,那么根据二叉搜索树的性质一定有...如下图所示,不平衡的原因是因为A的右孩子B的右子树插入了新结点而导致了A的不平衡,那么就要利用RR旋转来调整不平衡结点A,由于平衡二叉树一定是二叉搜索树,设定插入结点为C,那么根据二叉搜索树的性质一定有...如下图所示,不平衡的原因是因为A的左孩子B的右子树插入了新结点而导致了A的不平衡,那么就要利用LR旋转来调整不平衡结点A,由于平衡二叉树一定是二叉搜索树,设定插入结点为C,那么根据二叉搜索树的性质一定有...,那么只需在二叉搜索树的插入操作上添加判断结点是否平衡需要进行旋转处理即可。

65640

平衡二叉树

,判断该树是不是平衡二叉树。...如果某二叉树中任意节点的左右子树的深度相差不超过 1,那么它就是一棵平衡二叉树。...限制:0 <= 树的结点个数 <= 10000 基本知识点 二叉树的每个节点最多有两个子节点,平衡二叉树中任意一个节点的左右子树高度相差不能大于 1,满二叉树和完全二叉树都是平衡二叉树,普通二叉树有可能是平衡二叉树...题解 解法一 思路 若想判断二叉树是不是平衡二叉树,只需要判断左右子树的高度差是不是不超过 1 即可。同时,要满足一个树是平衡二叉树,它的子树也必须是平衡二叉树。...我们可以从根结点开始,通过递归来求得子树的高度,以及子树是否平衡二叉树,以此来结合判断二叉树是否平衡二叉树。 代码 /** * Definition for a binary tree node

36911

平衡二叉树

为了解决上面的问题,平衡二叉树(AVL树)就应运而生了。 2. 什么是平衡二叉树?...平衡二叉树又叫AVL树,也叫平衡二叉搜索树,可以保证较高的查询效率; 它是一棵空树,或者是左右子树的高度差的绝对值不会超过1,并且左右两棵子树都是一棵平衡二叉树平衡二叉树常用的实现算法有红黑树,AVL...如何创建平衡二叉树? (1)....左旋转思路: 假如现有数列:4,3,6,5,7,8,创建出来的二叉树排序数如下图: 二叉排序树 节点4的左子树高度为1,右子树高度为3,高度差是2,所以不是平衡二叉树。...如果要将其变成平衡二叉树该怎么做呢?因为其右子树的高度更高,要分点儿给左子树,所以方法叫做左旋转。

24810

4.5.2 平衡二叉树

1、平衡二叉树的定义 为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树,简称平衡树(AVL...定义结点左子树和右子树的高度差为该结点的平衡因子,则平衡二叉树结点的平衡因子的值只可能是-1、0或1。...因此平衡二叉树可定义为它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度差的绝对值不超过1. 2、平衡二叉树的插入 二叉排序树保证平衡的基本思想:每当在二叉树中插入...(或删除)一个结点时,首先要检查其插入路径上的结点是否因为此次操作而导致了不平衡。...可以证明,含有n个结点的平衡二叉树的最大深度为O(log2 n).因此平衡二叉树的平均查找长度为O(log2 n)。

44020
领券