題目

難度：★★☆☆☆
類型：二叉樹

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：

一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過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 。

解答

根據(jù)題目平衡二叉樹的定義，我們只需要保證每一個結點的左右子樹均平衡且最大深度差不大于1即可。這里我們可以使用【題目104. 二叉樹的最大深度】來計算每一棵子樹的最大深度，通過遞歸遍歷判斷各個結點是否平衡：

1. 當輸入的根結點為空時，該二叉樹平衡；

2. 調用本函數(shù)進行遞歸，當輸入結點的左右子樹均為平衡二叉樹，且最大深度差不大于1時，二叉樹平衡；

3. 返回結果。

class Solution:

    def isBalanced(self, root):

        def height(root):
            """
            獲得以root為根結點的樹的最大深度
            :param root:
            :return:
            """
            if root is None:
                return 0
            return max(height(root.left), height(root.right)) + 1

        def is_balanced(root):
            """
            判定是否為平衡二叉樹
            :param root:
            :return:
            """
            if root is None:        # 如果是空樹
                return True         # 一定是平衡二叉樹

            # 滿足平衡二叉樹的條件：左右子樹平衡，左右子樹最大深度差值不大于1
            return is_balanced(root.left) and is_balanced(root.right) and \
                   abs(height(root.left)-height(root.right)) <= 1

        return is_balanced(root)

如有疑問或建議，歡迎評論區(qū)留言~