# 104. Maximum Depth of Binary Tree

[https://leetcode.com/problems/maximum-depth-of-binary-tree/](https://leetcode.com/problems/maximum-depth-of-binary-tree/)

## solution

```python
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        l = self.maxDepth(root.left)
        r = self.maxDepth(root.right)
        return max(l, r) + 1
```

时间复杂度：O(n)\
空间复杂度：O(1)

## follow-up

[111. Minimum Depth of Binary Tree](https://leetcode.com/problems/minimum-depth-of-binary-tree/)

* BFS

```python
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        level = [root]
        depth = 1
        while level:
            this_level = []
            for i in level:
                if i.left is None and i.right is None:
                    return depth
                if i.left:
                    this_level.append(i.left)
                if i.right:
                    this_level.append(i.right)
            level = this_level
            depth += 1
```

时间复杂度：O(n)\
空间复杂度：O(n)

* DFS

```python
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        if not root.left:
            return self.minDepth(root.right) + 1
        if not root.right:
            return self.minDepth(root.left) + 1

        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
```

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

```python
# 类似求树的直径

class Solution:
    def __init__(self):
        self.res = True

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if not root:
            return 0

        l = self.dfs(root.left)
        r = self.dfs(root.right)
        if abs(l - r) > 1:
            self.res = False
        return max(l, r) + 1
```

时间复杂度：O(n)\
空间复杂度：O(h)

[Balance a Binary Search Tree](https://www.geeksforgeeks.org/convert-normal-bst-balanced-bst/)
