# 110 - Balanced Binary Tree

解法一 - Recursion

一棵 binary tree 如果是 balanced，那不僅是左右兩棵子樹的高度差不能超過 1，而且左右兩棵子樹也都得是 balanced tree。

所以在 isBalanced 中，我們不僅要判斷 heightDiff <= 1，同時也要確認左右兩棵子樹也都是 balanced。

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;

        int heightDiff = abs(level(root->left)-level(root->right));
        return (heightDiff <= 1) && isBalanced(root->left) && isBalanced(root->right);
    }

private:
    int level(TreeNode* root) {
        if(!root) return 0;

        return max(level(root->left), level(root->right))+1;
    }
};

這樣實作的優點是程式碼很簡單，但缺點就是每個 node 在被 isBalanced 檢驗時，都得對所有子孫 node 呼叫 level，所以 level() 會被重複呼叫很多次。上面的程式碼跑起來的效率如下：

Runtime: 20 ms, faster than 44.49% of C++ online submissions for Balanced Binary Tree. Memory Usage: 17.4 MB, less than 45.23% of C++ online submissions for Balanced Binary Tree.

解法二 - 用 memoization 改進解法一

我們可以額外使用一個 hash table 來儲存樹的高度，key 是 TreeNode*，value 就是高度，這樣就只需要計算一次：

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true; //empty tree is balanced

        int heightDiff = abs(level(root->left)-level(root->right));
        return (heightDiff <= 1) && isBalanced(root->left) && isBalanced(root->right);
    }

private:
    int level(TreeNode* root) {
        if(!root) return 0;

        if(table.find(root) != table.end())
            return table[root];

        int height = max(level(root->left), level(root->right))+1;    
        table.insert(pair<TreeNode*, int>(root, height));
        return height;
    }

    map<TreeNode*, int> table;
};

跑起來的效率如下：

Runtime: 24 ms, faster than 20.10% of C++ online submissions for Balanced Binary Tree. Memory Usage: 25.2 MB, less than 5.03% of C++ online submissions for Balanced Binary Tree.

雖然效率乍看之下比解法一還要慢，但我覺得這跟 Leetcode 的 testcase 也有很大關係，如果說 test case 都是很大的 tree，那 level 被重複呼叫的差異就會顯現出來。

解法三 - 只要一不 balanced 就回傳 -1，將時間複雜度減為 O(N)

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return level(root) != -1;
    }

private:
    int level(TreeNode* root) {
        if(!root) return 0;

        int leftHeight = level(root->left);
        if(leftHeight == -1)  return -1;
        int rightHeight = level(root->right);
        if(rightHeight == -1) return -1;

        if(abs(leftHeight - rightHeight) > 1) return -1;
        return max(leftHeight, rightHeight)+1;
    }
};

Runtime: 12 ms, faster than 95.02% of C++ online submissions for Balanced Binary Tree. Memory Usage: 17.6 MB, less than 11.54% of C++ online submissions for Balanced Binary Tree.