---
# System prepended metadata

title: 110. Balanced Binary Tree
tags: [Grind 169]

---

# 110. Balanced Binary Tree

> ***View the book with <i class="fa fa-book"></i> Book Mode.***

- [**LeetCode筆記目錄**](https://hackmd.io/@WeiYee/SyABdj_eA)

## :book: 題目

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

## :dart: 解題步驟
- 採用遞迴方式處理，並以 Preorder Traversal 遍歷節點。
    - 返回值 < 0 ，代表已經不符合 height - balanced
    - 返回值 > 0 代表當前 左、右子樹最大 level
- 如果當前節點為 null ，則返回 0
- 先查看左子樹，再查看右子樹
- 如果 **左、右子樹 返回值相差大於1** 或者 **至少一值為-1** ，則返回 -1
- 反之，返回 左、右子樹最大 level + 1

## :pencil2: 程式碼
### Java
```java=
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return (getHeight(root) != -1);
    }

    int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftValue = getHeight(root.left);
        int rightValue = getHeight(root.right);
        if (leftValue == -1 || rightValue == -1 || Math.abs(leftValue - rightValue) > 1) return -1;
        return Math.max(leftValue, rightValue) + 1;
    }
}
```