Programming Skills: Balanced Binary Tree

[題目]

https://leetcode.com/problems/balanced-binary-tree/description/

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

Return false.

定義balance為:每個node的左右子樹，高度差距不大於1

給你一個root，問你這棵樹是不是balance

[思路]

1.照題述的"every node"來看，你必須要爬過所有的tree node，對每一個node檢查"以我為root的子樹是否balance"。所以可想到要寫一個遞迴func來遊覽這棵樹的每一個點。
功能是回傳"我是否balance && 我的兩個子樹是否balance"。

2.照題述的"the depth of sub-tree"來看，我要寫一個func可以取得tree height。這可以用一個遞迴func，功能是回傳"我的高=我的子樹的高度+1"。

結合1,2兩點就可寫出下列code


class Solution {
public:
    

    bool isBalanced(TreeNode* root) {
        if(root==NULL) return true;
        if(abs(getH(root->left)-getH(root->right)) > 1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }

    int getH(TreeNode *root){
        if(root==NULL) return 0;
        return 1+max(getH(root->left), getH(root->right));
    }
    


};

1.會花費O(N)
2.會花費O(logN)
相乘就是O(NlogN)

[進階思路]

上面的方法直來直往很好懂，但是有個缺點是，由於計算高度的緣故，很多點會被重複接觸。例如下圖中，在計算node '1'的兩棵子樹的高度時，會接觸到最底層的node '4'。在計算node '2'的兩子樹高度時又再碰觸最底層的node '4'一次。這些重複計算都是多餘的行為。

讓我們來改善它一下。
我們觀察getH()中有一行

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

為了計算自己的高度，它會去取得左右子樹的高度。

這個時候不就可以算計左右子樹高度差，判斷是否平衡了嗎!!!

除此之外，你一旦在過程中發現某個子樹不平衡，按照定義這代表整棵樹不平衡。

因此你其實不用算其他子樹高了。所以這邊我們技巧性地return -1而不是子樹高，讓老爸知道它不用繼續算了。

這個做法中，當你接觸一個node時會同時"取得node的height" 與 "得知node是否balance"。因此每個node只要接觸一次即可。時間複雜度=O(N)。

結論 :
寫一個遞迴函式:"若左右子樹都平衡就回傳我的樹高，不然就回傳-1"


    
    bool isBalanced(TreeNode* root) {
        if(getH(root)==-1) return false;
        return true;
    } 

    int getH(TreeNode* root){
        if(root==NULL) return 0;
        int LH=getH(root->left);
        if(LH==-1) return -1;//no need to check other nodes anymore
        int RH=getH(root->right);
        if(RH==-1) return -1;//no need to check anymore

        //if subtrees are balance, chec if I am balance
        if(abs(LH-RH) > 1) return -1;
        else return 1+max(RH,LH);

    }