> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/divide-conquer/104.maximum-depth-of-binary-tree.md).

# 104.Maximum-Depth-of-Binary-Tree

## 104. Maximum Depth of Binary Tree

## 题目地址

<https://leetcode.com/problems/maximum-depth-of-binary-tree>

<http://www.lintcode.com/problem/maximum-depth-of-binary-tree/>

<http://www.jiuzhang.com/solutions/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.
```

## 代码

### Approach 1: Divide Conquer (Recursive)

**Intuition** By definition, the maximum depth of a binary tree is the maximum number of steps to reach a leaf node from the root node.

**Complexity analysis**

* Time complexity : we visit each node exactly once, thus the time complexity is O(*N*), where *N* is the number of nodes.
* Space complexity : in the worst case, the tree is completely unbalanced, *e.g.* each node has only left child node, the recursion call would occur *N* times (the height of the tree), therefore the storage to keep the call stack would be O(*N*). But in the best case (the tree is completely balanced), the height of the tree would be log(*N*). Therefore, the space complexity in this case would be O(log(*N*)).

```java
public class Solution {
    public int maxDepth(TreeNode root) {
    if (root == null) return 0;
  }

  int left = maxDepth(root.left);
  int right = maxDepth(root.right);
  return Math.max(left, right) + 1;
}
```

### Approach 2: Traverse

```java
class Solution {
  private int depth;

  public int maxDepth(TreeNode root) {
    depth = 0;
    helper(root, 1);

    return depth;
  }

  private void helper(TreeNode node, int curtDepth) {
    if (node == null) return;

    if (curtDepth > depth) {
      depth = curtDepth;
    }

    helper(node.left, curtDepth + 1);
    helper(node.right, curtDepth + 1);
  }
}
```

### Approach 3: Iteration

```java
class Solution {
  public int maxDepth(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<TreeNode> depths = new LinkedList<>();
    if (root == null)    return 0;

    stack.add(root);
    depths.add(1);

    int depth = 0;
    int current_depth = 0;
    while (!stack.isEmpty()) {
      root = stack.pollLast();
      current_depth = depths.pollLast();
      if (root != null) {
        depth = Math.max(depth, current_depth);
        stack.add(root.left);
        stack.add(root.right);
        depths.add(current_depth + 1);
        depths.add(current_depth + 1);
      }
    }

    return depth;
  }
}
```