# 110. Balanced Binary Tree

### Leetcode

<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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/10/06/balance_2.jpg)

```
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
```

**Example 3:**

```
Input: root = []
Output: true
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

Top-down recursion

創建一個 getHeight 的 function 幫助取得高度

```
const getHeight = function(node) {
    if (!node) return 0;

    const leftH = getHeight(node.left);
    const rightH = getHeight(node.right);

    return Math.max(leftH, rightH) + 1;
};

var isBalanced = function(root) {
    if (!root) return true;
    
    const leftH = getHeight(root.left);
    const rightH = getHeight(root.right);
    
    return Math.abs(leftH - rightH) <= 1 && isBalanced(root.left) && isBalanced(root.right);
};
```

Runtime: 97 ms, faster than 64.27% of JavaScript online submissions for Balanced Binary Tree.

Memory Usage: 46.9 MB, less than 79.06% of JavaScript online submissions for Balanced Binary Tree.

* **方法二**

Bottom-up recursion

方法一有個缺點是從上而下算的 getHeight 到下層子節點時又會被重新計算，所以方法二使用 bottom-up 方法計算高度，並將每個子節點的高度記錄下來避免重複計算高度

```
const helper = (node) => {
    if (!node) return [true, 0];
    
    const [isLeftBalanced, leftH] = helper(node.left);
    if (!isLeftBalanced) return [false, 0];
    
    const [isRightBalanced, rightH] = helper(node.right);
    if (!isRightBalanced) return [false, 0];
    
    return [Math.abs(leftH - rightH) <= 1, Math.max(leftH, rightH) + 1] 
}

var isBalanced = function(root) {
    return helper(root)[0];
};
```

Runtime: 90 ms, faster than 72.49% of JavaScript online submissions for Balanced Binary Tree.

Memory Usage: 49.4 MB, less than 7.67% of JavaScript online submissions for Balanced Binary Tree.
