題目介紹

描述：

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

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

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

解題思路：

遞歸算法的關(guān)鍵是要明確函數(shù)的「定義」是什么，然后相信這個定義，利用這個定義推導(dǎo)最終結(jié)果。

寫樹相關(guān)的算法，簡單說就是，先搞清楚當(dāng)前 root 節(jié)點該做什么，然后根據(jù)函數(shù)定義遞歸調(diào)用子節(jié)點，遞歸調(diào)用會讓孩子節(jié)點做相同的事情。

二叉樹題目的一個難點在于如何通過題目的要求思考出每一個節(jié)點需要做什么

平衡二叉樹的定義是：二叉樹的每個節(jié)點的左右子樹的高度差的絕對值不超過 11，則二叉樹是平衡二叉樹。根據(jù)定義，一棵二叉樹是平衡二叉樹，當(dāng)且僅當(dāng)其所有子樹也都是平衡二叉樹，因此可以使用遞歸的方式判斷二叉樹是不是平衡二叉樹，遞歸的順序可以是自頂向下或者自底向上。

對于當(dāng)前遍歷到的節(jié)點，首先計算左右子樹的高度，如果左右子樹的高度差是否不超過 11，再分別遞歸地遍歷左右子節(jié)點，并判斷左子樹和右子樹是否平衡。這是一個自頂向下的遞歸的過程。

自己的解法實現(xiàn)

def isBalanced(self, root):
        def getHeight(node):
            if not node: return 0
            return max(getHeight(node.left), getHeight(node.right)) + 1
        if not root: return True
        return abs(getHeight(root.left) - getHeight(root.right)) < 1 and self.isBalanced(root.left) \\
               and self.isBalanced(root.right)

網(wǎng)上比較優(yōu)秀的解法

解法一

自底向上遞歸的做法類似于后序遍歷，對于當(dāng)前遍歷到的節(jié)點，先遞歸地判斷其左右子樹是否平衡，再判斷以當(dāng)前節(jié)點為根的子樹是否平衡。如果一棵子樹是平衡的，則返回其高度（高度一定是非負(fù)整數(shù)），否則返回 -1?1。如果存在一棵子樹不平衡，則整個二叉樹一定不平衡。

def isBalanced2(self, root):
        def height(node):
            if not node: return 0
            leftHeight = height(node.left)
            rightHeight = height(node.right)
            if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:
                return -1
            else:
                return max(leftHeight, rightHeight) + 1
        return height(root) >= 0

解法二

同時返回深度和是否平衡

def isBalanced3(self, root):
        def _isBalanced(node):
            if not node: return 0, True
            if not root.left and not root.right: return 1, True

            l_depth, l_is_balanced = _isBalanced(node.left)
            r_depth, r_is_balanced = _isBalanced(node.right)
            return max(l_depth, r_depth) + 1, l_is_balanced and r_is_balanced \\
                   and abs(l_depth - r_depth) <= 1

        depth, _is_balaned =  _isBalanced(root)
        return _is_balaned

相關(guān)知識總結(jié)和思考

相關(guān)知識：

BFS：廣度/寬度優(yōu)先。其實就是從上到下，先把每一層遍歷完之后再遍歷一下一層。

可以使用Queue的數(shù)據(jù)結(jié)構(gòu)。我們將root節(jié)點初始化進隊列，通過消耗尾部，插入頭部的方式來完成BFS。

二叉搜索樹（BST）的特性：

1. 若它的左子樹不為空，則所有左子樹上的值均小于其根節(jié)點的值
2. 若它的右子樹不為空，則所有右子樹上的值均大于其根節(jié)點得值
3. 它的左右子樹也分別為二叉搜索樹

遞歸與迭代的區(qū)別

遞歸：重復(fù)調(diào)用函數(shù)自身實現(xiàn)循環(huán)稱為遞歸； 迭代：利用變量的原值推出新值稱為迭代，或者說迭代是函數(shù)內(nèi)某段代碼實現(xiàn)循環(huán)；