当前位置: 首页 > article >正文

【LeetCode110】平衡二叉树

题目描述

给定一个二叉树,判断它是否是 平衡二叉树

思路与算法

二叉树是平衡的,如果对于每个节点,它的左子树和右子树之间的高度差最多为 1。
注意:根据上述定义,单独计算根节点的左右子树高度,然后进行高度比较,是不对的。
所以应该递归地确定每个子树的高度;同时,检查每个节点的平衡条件。(两个动作)

创建一个辅助函数(我们称之为 checkBalance )

  • 如果子树是平衡的,返回其高度
  • 如果是不平衡的,返回特殊值(比如-1)
  1. base case: 如果一个节点是 None ,那么它是一个高度为 0 的空子树。这被认为是平衡的。
  2. 递归步骤
    • 对于给定的节点,递归计算其左子树和右子树的高度。
    • 检查当前节点是否平衡
      • 如果左子树或右子树不平衡(即,递归调用返回 -1),那么当前节点的子树也不平衡——立即返回 -1。
      • 如果两个子树都是平衡的,那么检查它们高度之间的差异
      • 如果差值超过 1,则以当前节点为根的树是不平衡的;返回 -1
      • 否则,当前节点的高度是其左子树和右子树高度的最大值加 1。
  3. 结果整合
    Once the helper function completes for the root
    • 如果返回 -1,则树是不平衡的
    • 否则,树是平衡的

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:

        def checkBalance(node: TreeNode) -> int:
            # base case
            if not Node:
                return 0
            
            leftHight = checkBalance(node.left)
            if leftHight == -1:
                return -1
            
            rightHeight = checkBalance(node.right)
            if rightHeight == -1:
                return -1
            
            if abs(leftHight - rightHeight) > 1:
                return -1
            
            return 1 + max(leftHight, rightHeight)
        return checkBalance(root) != -1
        

总结与反思

  1. 将明确定义的递归步骤转换为代码或伪代码
    • 书写base case(s)
      • Clearly define the simplest case(s) where the answer is known
      • 在代码中,这通常以一个 if 语句的形式出现,该语句check base case 并立即返回一个值。
    • 如果f(n)是你的函数,展示f(n)是如何依赖f(n-1)或其它实例的
    • 通过arithmetic operations, concatenation, or some form of aggregation.合并子问题结果
  2. 何时考虑使用辅助函数进行代码实现?
    • 如果你的递归解决方案需要额外的信息(例如当前深度、边界或任何其他状态),而这些信息不属于原始函数的签名,那么使用辅助函数是个好主意。当你想要将复杂性隐藏在主接口之外,或者使代码更有组织和模块化时,也可以使用辅助函数。
      • 例如,在平衡二叉树问题中,辅助函数返回子树的高度和一个标志,指示子树是否平衡。这些额外的信息在原始函数签名中并未提供,因此将递归逻辑封装在辅助函数中可以保持主函数的接口简洁。
      • 在平衡树检查中,主函数 isBalanced 只需要知道辅助函数返回的是有效高度还是特殊值(如 -1),就可以判断是否平衡
  3. 递归实现时,哪些内容可以放入辅助函数?
    • 包括核心递归算法:基本情况、递归调用、子问题结果的组合,以及在递归过程中必须保持的任何额外状态或信息。

http://www.kler.cn/a/588856.html

相关文章:

  • 爬虫获取 item_get_video 接口数据:小红书笔记视频详情的深度解析
  • Docker 端口映射的 “隐藏炸弹“ 与安全访问方案
  • 第二十七天 实践分布式任务调度,实现一个简单的分布式任务
  • Linux内核邻接子系统分析
  • PHP与前端框架的无缝集成:最佳实践与案例分析
  • 【Linux篇】初识Linux指令(下篇)
  • 【部署】ubuntu部署olmOCR
  • DICT领域有哪些重要的技术标准和规范?
  • 国科大——计网(0812)——考试真题
  • 96.HarmonyOS NEXT工具类设计模式教程:最佳实践与实现
  • 项目--五子棋(前置知识)
  • win32汇编环境,对 WM_MOUSEMOVE 消息的理解
  • kotlin中的界面组件
  • 视频编码中视频帧的类型解析
  • (分块)洛谷 P2801 教主的魔法 题解
  • 上传本地项目到GitHub
  • windows系统amd核显机器安装cpu版本pytorch(仅用于学习)
  • 迁移Kubuntu到thinkbook14+ 2025
  • 设计模式在MyBatis中的具体应用与分析
  • [ISP] 人眼中的颜色