LeetCode題目：110. 平衡二叉樹

題目要求如下 ↓ ↓ ↓ ↓ ：

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

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

一個二叉樹每個節(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 

結(jié)題思路

遞歸實現(xiàn)

• 1、得到任意節(jié)點的深度
• 2、計算出root節(jié)點的左右子節(jié)點的深度
• 3、abs(left - right) > 1 進(jìn)行判斷

/// Swift 代碼實現(xiàn)
class Solution {
    /// 遞歸實現(xiàn)
    func isBalanced(_ root: TreeNode?) -> Bool {
        guard let root = root else {
            return true
        }
        return height(ofNode: root) >= 0
    }
    
    /// 輸出節(jié)點的深度
    func height(ofNode root: TreeNode?) -> Int {
        guard let root = root else {
            return 0
        }
        // 初始深度
        let sum = 1
        let leftHeight = height(ofNode: root.left)
        let rightHeight = height(ofNode: root.right)
        if leftHeight >= 0 && rightHeight >= 0 && abs(leftHeight - rightHeight) <= 1{
            return sum + max(leftHeight, rightHeight)
        }else{
            return -1
        }
    }
}

image.png

算法思想

• 分治法（divide and conquer method）
  • 通俗講，分而治之。把一個大的問題分解成N個小問題，逐個擊破。
  • 把問題分解到足夠小，小到很容易求解為止，然后再將子問題合并成更大規(guī)模的問題的解。
  • 自底向上逐步求解出原來問題的解。