No. 110 - Balanced Binary Tree
====


---

## [LeetCode 110 -- Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)

### 題目描述

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 left and right subtrees of every node differ in height by no more than 1.

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

---

本題目的是要檢查給定的 tree，它每個 node 的左右 subtree 是不是平衡。這邊平衡的意思就是左右 subtree 的高相差不超過 1。

### 解法

要比較每個 node 的左右 subtree 是不是平衡的，我們需要先算出它們的高，接著再把他們彼此相減比較是否平衡。

我們設計一個函式如下:

bool _isBalanced(TreeNode *node, int &height);

它的回傳值是 boolean 值，目的是回傳當前 `node` 的左右 subtree 是否平衡，並且帶有另外一個參數 `height` 來知道當前的 subtree 的高。

這個函式的做法如下:

bool _isBalanced(TreeNode *root, int &height) {
  if (!root)
    return true;
  int lh = 0;
  int rh = 0;
  if (!_isBalanced(root->left, lh) || // check if left subtree is balanced.
      !_isBalanced(root->right, rh))  // check if right subtree is balanced.
    return false; // if subtree is unbalanced, then the tree is unbalanced.
  height = max(lh, rh) + 1; // calculate tree height
  return abs(lh - rh) <= 1; // compare that if current subtree is balanced.
}

此函式的第 6 行會 recursive 的去確認每個 node 的左右 subtree 是否平衡，也就是會從 leaf 開始 bottom up 的比對每一層 tree node 的 subtree 是否平衡。一旦發現有個 node 的 subtree 不平衡，那整個 tree 就是不平衡。

倘若左右 subtree 都是平衡的，第 9 行就會算出當前 subtree 的高，並且第 10 行會比較這個 subtree 是否是平衡的。

完整程式碼如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool _isBalanced(TreeNode *root, int &height) {
      if (!root)
        return true;
      int lh = 0;
      int rh = 0;
      if (!_isBalanced(root->left, lh) || // check if left subtree is balanced.
          !_isBalanced(root->right, rh))  // check if right subtree is balanced.
        return false; // if subtree is unbalanced, then the tree is unbalanced.
      height = max(lh, rh) + 1; // calculate tree height
      return abs(lh - rh) <= 1; // compare that if current subtree is balanced.
    }
    bool isBalanced(TreeNode* root) {
      int height = 0;
      return _isBalanced(root, height);
    }
};

### 複雜度分析

這個 recursive 的作法是 one pass 完成比較平衡並且同時計算 tree 高，所以 `_isBalanced` 函式被呼叫的次數就是 node 的數量，時間複雜度為 $O(N)$。

空間複雜度上為 $O(H)$， $H$ 為 tree 的高。