Maximum Depth of Binary Tree

Given the root of a binary tree, return 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.

Function signature

func MaxDepth(root *TreeNode) int

TreeNode definition

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

Examples

Example 1:

Input:
    3
   / \
  9  20
    /  \
   15   7

Output: 3
Explanation: The longest path is 3 → 20 → 15 (or 3 → 20 → 7), which has 3 nodes.

Example 2:

Input:
  1
   \
    2

Output: 2

Example 3:

Input: nil (empty tree)
Output: 0

Constraints

• The number of nodes in the tree is in the range [0, 10000]
• -100 <= Node.val <= 100

Hints

1. Think recursively: what is the depth of a nil node?
2. The depth of a node is 1 + the maximum depth of its children.

Notes

• This is a classic tree recursion problem. The key is to think about the base case (nil returns 0) and the recursive case (1 + max of children).