日野弥生：勉強しよう

LeetCode 110 - 平衡二叉树

发表于2025年03月01日

递归解题，首先搞清楚平衡二叉树的理念，很明显是要比较左右子树的树高，从而判断最好使用后序遍历的深度优先搜索。同时利用技巧判断平衡。即，一旦发现不满足平衡时，把深度置为-1，从而可以快速判断是否整棵树所有节点都满足。

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def getHeight(root:Optional[TreeNode]) -> int:
            if root is None:
                return 0
            leftHeight = getHeight(root.left)
            rightHeight = getHeight(root.right)
            # 如果有子树出现-1，则代表不满足
            if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:
                return -1
            return max(leftHeight, rightHeight) + 1
        return getHeight(root) != -1

フラッシュタブ：LeetCode

题目链接：https://leetcode.cn/problems/balanced-binary-tree/

日野弥生：勉強しよう

LeetCode 110 - 平衡二叉树

LeetCode 617 - 合并二叉树

LeetCode 965 - 单值二叉树