【LeetCode 110.平衡二叉樹】兩種遞歸實作：自頂向下、自底向上

題目描述：給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過 1。

解法 1: 自頂向下

根絕平衡二叉樹的定義，可以遞歸比較每個節點的左右子樹的高度差，是否超過 1。如果所有節點都滿足條件，那麼就是一棵平衡二叉樹；否則，不是一棵平衡二叉樹。

這裡計算二叉樹高度的思路在《LeetCode 104.二叉樹的最大深度》中有介紹兩種方法（遞歸、層序周遊），這裡不再冗述。

代碼實作如下：

// ac位址：https://leetcode-cn.com/problems/balanced-binary-tree/
// 原文位址：https://xxoo521.com/2020-03-23-balanced-tree
/**
 * 判斷是否是平衡二叉樹
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    if (!root) return true;
    return (
        isBalanced(root.left) &&
        isBalanced(root.right) &&
        Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
    );
};

/**
 * 擷取二叉樹的高度
 * @param {TreeNode} root
 * @return {number}
 */
function maxDepth(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}           

複制

解法 2: 自底向上（推薦）

你可能已經發現解法 1 的問題了：每個節點的高度值都會被重複計算。這帶來了額外的時間消耗。那麼如何避免這些重複計算呢？

解決思路是：先計算左右子樹是否是平衡二叉樹，并且計算、儲存左右子樹的高度，那麼目前二叉樹的高度可以通過左右子樹的高度直接計算出來。

在 JavaScript 中，想要儲存過程中的計算結果非常簡單：可以通過傳遞一個對象作為參數，其上有屬性 depth，表示以目前節點為根節點的二叉樹的高度。

代碼實作如下：

// ac位址：https://leetcode-cn.com/problems/balanced-binary-tree/
// 原文位址：https://xxoo521.com/2020-03-23-balanced-tree
/**
 * @param {TreeNode} root
 * @param {Object} obj
 * @return {boolean}
 */
var isBalanced = function(root, obj = {}) {
    if (!root) {
        obj.depth = 0;
        return true;
    }

    const left = {}; // 左子樹資訊
    const right = {}; // 右子樹資訊
    if (isBalanced(root.left, left) && isBalanced(root.right, right)) {
        if (Math.abs(left.depth - right.depth) > 1) {
            // 檢查左右子樹高度差
            return false;
        }

        obj.depth = Math.max(left.depth, right.depth) + 1; // 目前二叉樹的高度
        return true;
    } else {
        return false;
    }
};           

複制