題目描述

輸入一棵二叉樹的根節點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意節點的左右子樹的深度相差不超過 1，那么它就是一棵平衡二叉樹。

• 1 <= 樹的結點個數 <= 10000

題目樣例

示例

給定二叉樹 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

給定二叉樹 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

題目思考

1. 可以只需要遍歷一遍節點得到結果嗎?

解決方案

思路

• 有了昨天                 劍指 Offer 55 - I. 二叉樹的深度 - leetcode 劍指 offer 系列的鋪墊, 這道題相信大家都可以迎刃而解
• 一個比較容易想到的思路是: 先計算出每個節點的深度, 并將其存入                 節點=>深度字典中; 然后再遍歷一遍節點, 針對每個節點, 判斷它左右子節點的深度是否滿足要求, 所有節點都滿足的話才說明平衡. 但是這種方案需要遍歷兩邊節點, 效率不太高, 如何一次性遍歷得出結果呢?
• 回顧遞歸求深度的方案, 我們是先求得左右子樹的深度, 然后才進一步得到當前節點的深度, 所以我們就可以直接加一個全局變量記錄當前是否平衡, 并額外引入一個邏輯來比較子樹深度, 如果不滿足要求, 則直接把變量置為 false 直接返回即可
• 注意本題并不適用于 BFS 迭代求深度的算法, 因為迭代方案求的是當前節點                 從上到下所在的層數, 每個節點并不知道自己的深度(從下往上, 從葉子節點到自身)究竟是多少, 所以無從判斷是否平衡
• 下面代碼對必要的步驟有詳細的解釋, 方便大家理解

復雜度

• 時間復雜度 O(N): 需要遍歷整個樹
• 空間復雜度 O(H): H 表示樹的高度, 也即遞歸的棧的消耗

代碼

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # 遞歸, 邊求深度邊判斷, 返回深度, 全局變量標記當前是否平衡
        balance = True

        def getDepth(node):
            nonlocal balance
            if not node or not balance:
                # 遞歸出口: 如果節點為空或者不平衡, 返回0, 無需繼續遞歸了
                return 0
            ldepth = getDepth(node.left)
            rdepth = getDepth(node.right)
            if abs(ldepth - rdepth) > 1:
                # 不平衡, 全局變量設為false
                balance = False
            # 返回當前節點自身的深度
            return max(ldepth, rdepth) + 1

        getDepth(root)
        return balance