# 110. Balanced Binary Tree

{% hint style="success" %}

1. Both of left and right subtrees are balanced?
2. max depth difference between left and right <= 1?
   {% endhint %}

### Solution 1:

1. Write maxDepth function to get the max depth of left and right subtrees
2. In main function, recusive to see each layer's balance and compute left and right maxDepth difference

{% tabs %}
{% tab title="Python效率低" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # edge case
        if root == None:
            return True

        # regular case
        if abs(self.maxHeight(root.left) - self.maxHeight(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

    def maxHeight(self, root):
        if root == None:
            return 0
        
        return max(self.maxHeight(root.left), self.maxHeight(root.right))+1
```

{% endtab %}
{% endtabs %}

### Solution 2:

Help function: if one of left and right subtree is not balanced, or max depth difference > 1, return -1; otherwise return maxDepth.

Main function: return `true` or `false` according to help function.

{% tabs %}
{% tab title="Python效率极高" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.getHeight(root) != -1

    def getHeight(self, root):
        # edge case
        if root == None:
            return 0
        
        # regular case
        left = self.getHeight(root.left)
        right = self.getHeight(root.right)
        
        if left == -1 or right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        
        return max(left, right)+1
```

{% endtab %}

{% tab title="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;
 *     }
 * }
 */

final class TreeInfo {
    public final int height;
    public final boolean balanced;
    
    public TreeInfo(int height, boolean balanced) {
        this.height = height;
        this.balanced = balanced;
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        TreeInfo res = helper(root);
        return res.balanced;
    }
    
    private TreeInfo helper(TreeNode root) {
        if(root == null) return new TreeInfo(0, true);
        
        TreeInfo resLeft = helper(root.left);
        TreeInfo resRight = helper(root.right);
        
        if(!resLeft.balanced || !resRight.balanced)
            return new TreeInfo(0, false);
        else {
            if(Math.abs(resLeft.height - resRight.height) > 1)
                return new TreeInfo(0, false);
            else
                return new TreeInfo(Math.max(resLeft.height, resRight.height) + 1, true);
        }
    }
}
```

{% endtab %}
{% endtabs %}

时间复杂度= $$O(n)$$ 分析：1. 每个节点要做的运算是 $$O(1)$$ ；2. 每个节点只做一次运算，无重复，一共有 $$n$$ 个节点，所以是 $$O(n)$$ ；3. 则 $$T=O(1)\*O(n)=O(n)$$ .