营销型企业网站特点,住房和城乡建设部网站31号文,ui设计属于视觉传达吗,小米发布会在哪看目录#xff1a;
目的
思路
复杂度
记忆秘诀
python代码 目的#xff1a; 输入一棵节点数为 n 二叉树#xff0c;判断该二叉树是否是平衡二叉树。 思路 什么是平衡二叉树#xff08;AVL 树#xff09;#xff1f; 每个节点的左子树和右子树的高度差不能超过 1。确保…目录
目的
思路
复杂度
记忆秘诀
python代码 目的 输入一棵节点数为 n 二叉树判断该二叉树是否是平衡二叉树。 思路 什么是平衡二叉树AVL 树 每个节点的左子树和右子树的高度差不能超过 1。确保了在进行查找、插入和删除操作时时间复杂度保持在O(log n)从而提高了数据处理的效率。 举例子 1/ \2 3/ \
4 5这个树是平衡二叉树
对于节点 1它的左子树高度是 2右子树高度是 1差值是 1符合平衡条件。对于节点 2它的左子树高度是 1右子树高度是 1差值是 0符合平衡条件。对于节点 3它的左右子树都为空高度差是 0符合平衡条件。 1/ 2 / 3 这个树不是平衡二叉树对于节点 1它的左子树高度是 2右子树高度是 0差值是 2超过了 1违反了平衡条件说明这棵树不平衡。 代码逻辑递归深度优先搜索DFS 递归计算每个节点的子树高度如果节点为空None那么高度为 0并且认为空树是平衡的。 递归计算左子树和右子树的高度 先计算左子树的高度。如果左子树不平衡返回值为 -1直接返回 -1表示树不平衡。接着计算右子树的高度。如果右子树不平衡返回值为 -1同样返回 -1。 检查当前节点是否平衡 对于当前节点检查左右子树高度差的绝对值是否大于 1。如果大于 1则表示当前节点不平衡返回 -1。 返回当前节点的高度 如果当前节点平衡则返回该节点的高度节点高度等于左右子树高度的最大值 1。 最终判断树是否平衡 调用递归函数check_balance 对整个树进行判断。如果树的根节点返回的值不是 -1则说明树是平衡的返回 True。否则返回 False。 示例 1/ \2 3/ \4 5
递归过程 从根节点开始检查节点 1首先要检查左子树节点 2和右子树节点 3。 检查节点 2继续检查左子树节点 4和右子树节点 5。 检查节点 4节点 4 没有子节点所以它的高度是 0。 检查节点 5节点 5 也没有子节点它的高度是 0。 回到节点 2 左子树高度是 0节点 4右子树高度是 0节点 5。abs(0 - 0) 0符合平衡条件返回节点 2 的高度为 1max(0, 0) 1。 检查节点 3节点 3 没有子节点所以它的高度是 0。 回到根节点 1 左子树高度是 1节点 2右子树高度是 0节点 3。abs(1 - 0) 1符合平衡条件返回节点 1 的高度为 2max(1, 0) 1。
所有节点的左右子树高度差都不超过 1因此这棵树是平衡二叉树最终返回 True。 复杂度 时间复杂度O(n 对每个节点只进行了访问一次其中 n 是树中的节点数。 空间复杂度O(h) h 是树的高度。递归调用栈的最大深度为树的高度。在最坏情况下树是单链状空间复杂度为 O(n)在平均情况下空间复杂度为 O(log n)如果树比较平衡的话。 记忆秘诀 递归深度优先搜索计算每个节点的左右子树的高度。检查高度差是否小于等于1如果某个子树不平衡立即返回 -1 表示不平衡若平衡则返回该子树的高度。 python代码
class TreeNode:def __init__(self, x):self.val xself.left Noneself.right Noneclass Solution:def IsBalanced_Solution(self, pRoot: TreeNode) - bool:def check_balance(node):# 空树是平衡的高度为 0if not node:return 0# 递归计算左右子树高度left_height check_balance(node.left)if left_height -1: # 左子树不平衡return -1right_height check_balance(node.right)if right_height -1: # 右子树不平衡return -1# 检查当前节点的平衡性if abs(left_height - right_height) 1:return -1 # 当前节点不平衡# 返回当前节点的高度return max(left_height, right_height) 1return check_balance(pRoot) ! -1 # 如果返回值不是 -1则树是平衡的* 欢迎大家探讨新思路能够更好的理解和记忆
