# 110. Balanced Binary Tree
## 題目概述
Given a binary tree, determine if it is height-balanced.
## 測資
### Example 1:

**Input:** root = [3,9,20,null,null,15,7]
**Output:** true

### Example 2:

**Input:** root = [1,2,2,3,3,null,null,4,4]
**Output:** false
### Example 3:

**Input:** root = []
**Output:** true
## 作法
這題雖然是easy，但在做法上其實不是那麼直觀，因為定義的"height-balanced"是針對"所有節點"，代表我們應該要從樹葉慢慢檢查上來，要先讓指標跑到樹葉的地方才行。

首先我們定義一下計算左右子樹樹高的函式(DFS)：

int height(struct TreeNode* t, int h){
    if(t==NULL) return h;
    else return max(height(t->left,h+1),height(t->right,h+1)); 
}

接下來看題目函式，我們用遞迴呼叫的方式讓指標往樹葉靠，當靠到樹葉在進行回傳：

bool isBalanced(struct TreeNode* root) {
    if(root==NULL) return true; //測資三條件

    if(isBalanced(root->left) && isBalanced(root->right)) //這行讓指標移動到leaf
        return abs(height(root->left,0)-height(root->right,0))<=1; //開始檢驗子樹樹高
    else return false; //發現節點不平衡
}

最後把isBalanced()最後兩行的邏輯合併，就會變成下面這個樣子，因為函式不用分開呼叫，所以複雜度會進一步降低。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define max(a,b) a>b?a:b
int height(struct TreeNode* t, int h){
    if(t==NULL) return h;
    else return max(height(t->left,h+1),height(t->right,h+1)); 
}

bool isBalanced(struct TreeNode* root) {
    if(root==NULL) return true;
    return isBalanced(root->left) && isBalanced(root->right) && abs(height(root->left,0)-height(root->right,0))<=1;
}