# 104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

**Note:** A leaf is a node with no children.

**Example:**

Given binary tree `[3,9,20,null,null,15,7]`,

```
    3
   / \
  9  20
    /  \
   15   7
```

return its depth = 3.

```cpp
// Recursion
int maxDepth(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
```

```cpp
// Recursion
int maxDepth(TreeNode* root) { // time: O(n); space: O(n)
    int res = -1, cur = 0;
    helper(root, cur, res);
    return res == -1 ? 0 : res;
}
void helper(TreeNode* root, int cur, int& res) {
    if (!root) return;
    ++cur;
    if (!root->left && !root->right) {
        // cout << "root node: " << root->val << endl;
        // cout << "res: " << res << ", cur: " << cur << endl;
        res = max(res, cur);
        // cout << "after update, res: " << res << endl;
    }
    helper(root->left, cur, res);
    helper(root->right, cur, res);
}
```

```cpp
// Iteration
int maxDepth(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int res = 0;
    while (!q.empty()) {
        ++res;
        int n = q.size();
        for (int i = 0; i < n; ++i) {
            TreeNode* cur = q.front(); q.pop();
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return res;
}
```