【LeetCode110】平衡二叉树
题目描述
给定一个二叉树,判断它是否是 平衡二叉树
思路与算法
二叉树是平衡的,如果对于每个节点,它的左子树和右子树之间的高度差最多为 1。
注意:根据上述定义,单独计算根节点的左右子树高度,然后进行高度比较,是不对的。
所以应该递归地确定每个子树的高度;同时,检查每个节点的平衡条件。(两个动作)
创建一个辅助函数(我们称之为 checkBalance )
- 如果子树是平衡的,返回其高度
- 如果是不平衡的,返回特殊值(比如-1)
- base case: 如果一个节点是 None ,那么它是一个高度为 0 的空子树。这被认为是平衡的。
- 递归步骤
- 对于给定的节点,递归计算其左子树和右子树的高度。
- 检查当前节点是否平衡
- 如果左子树或右子树不平衡(即,递归调用返回 -1),那么当前节点的子树也不平衡——立即返回 -1。
- 如果两个子树都是平衡的,那么检查它们高度之间的差异
- 如果差值超过 1,则以当前节点为根的树是不平衡的;返回 -1
- 否则,当前节点的高度是其左子树和右子树高度的最大值加 1。
- 结果整合
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
总结与反思
- 将明确定义的递归步骤转换为代码或伪代码
- 书写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.合并子问题结果
- 书写base case(s)
- 何时考虑使用辅助函数进行代码实现?
- 如果你的递归解决方案需要额外的信息(例如当前深度、边界或任何其他状态),而这些信息不属于原始函数的签名,那么使用辅助函数是个好主意。当你想要将复杂性隐藏在主接口之外,或者使代码更有组织和模块化时,也可以使用辅助函数。
- 例如,在平衡二叉树问题中,辅助函数返回子树的高度和一个标志,指示子树是否平衡。这些额外的信息在原始函数签名中并未提供,因此将递归逻辑封装在辅助函数中可以保持主函数的接口简洁。
- 在平衡树检查中,主函数 isBalanced 只需要知道辅助函数返回的是有效高度还是特殊值(如 -1),就可以判断是否平衡
- 如果你的递归解决方案需要额外的信息(例如当前深度、边界或任何其他状态),而这些信息不属于原始函数的签名,那么使用辅助函数是个好主意。当你想要将复杂性隐藏在主接口之外,或者使代码更有组织和模块化时,也可以使用辅助函数。
- 递归实现时,哪些内容可以放入辅助函数?
- 包括核心递归算法:基本情况、递归调用、子问题结果的组合,以及在递归过程中必须保持的任何额外状态或信息。