程序员面试金典 - 面试题 04.04. 检查平衡性

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

      1
     / \
    2   2
   / \
  3   3
 / \
4   4

返回 false 。

题目思考

1. 需要定义哪些辅助函数?

解决方案

思路

• 根据题目描述, 显然需要通过利用当前节点的高度来判断是否平衡
• 所以引入一个函数来得到当前节点高度, 然后判断左右子树的高度差是否超过 1 来判断是否平衡
• 这里有一个小技巧, 可以将计算高度和判断平衡合二为一: 即如果当前树不平衡的话返回-1, 否则返回正常高度值. 因为正常的高度值都是非负数, 所以 -1 一定可以代表不平衡的状态
• 这样最后只需要比较根节点调用函数后的返回值是否为-1 来判断整个树是否平衡了

复杂度

• 时间复杂度 O(N): 每个节点只需要遍历一遍
• 空间复杂度 O(logN): 递归栈的消耗, 递归深度最多是树的高度, 也即 logN

代码

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # 合并计算高度和平衡性判断
        def getHeight(node):
            # 不平衡时返回-1, 否则返回当前节点的高度
            if not node:
                return 0
            lh, rh = getHeight(node.left), getHeight(node.right)
            if lh == -1 or rh == -1 or abs(lh - rh) > 1:
                # 如果1.左子树不平衡; 2. 右子树不平衡; 3.左右子树高度差绝对值大于1
                # 则说明当前树不平衡, 返回-1
                return -1
            # 到这里说明当前树平衡, 且lh和rh都是正常的高度, 它们之中较大值+1即为当前树的高度
            return 1 + max(lh, rh)

        # 最后判断root节点是否返回-1即可
        return getHeight(root) != -1

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊