---
# System prepended metadata

title: 'LeetCode #110 [Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)'
tags: [Recursion, LeetCode, Easy, Tree]

---

###### tags: `LeetCode` `Tree` `Recursion` `Easy`
# LeetCode #110 [Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)
### (Easy)
給定一個二元樹，判斷它是否是高度平衡的二元樹。

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

`一個二元樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 。`


---
利用遞迴法
本題需要額外兩個遞迴函式, 分別計算樹的高度以及確認左右子樹是否平衡。
確認左右子樹是否平衡函示的判斷調件(有先後順序):
```
若左右節點皆為空節點, 則回傳true
若左右有一節點為空節點, 則看另一節點的高度, 高度為一則回傳true, 大於1則回傳false
若左右節點皆不為空節點且平衡, 則繼續比對左右節點各自的左右節點是否平衡
其餘狀態皆回傳false
```

---
```
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root)return true;
        return check(root->left, root->right);
    }
    bool check(TreeNode* leftnode, TreeNode* rightnode){
        if(!leftnode&&!rightnode)return true;
        else if (!leftnode&&countdepth(rightnode)==1) return true;
        else if (!rightnode&&countdepth(leftnode)==1) return true;
        else if(abs(countdepth(leftnode)-countdepth(rightnode))<=1)return check(leftnode->left,leftnode->right)&&check(rightnode->left, rightnode->right);
        else return false;
    }
    int countdepth(TreeNode* node){
        if(!node)return 0;
        return max(countdepth(node->left), countdepth(node->right))+1;
    }
};
```