LeetCode官方题解及解析：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],

return its depth = 3.

# 解答1[Java]：递归算法

## 复杂度分析

• 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))$

completely unbalanced would looks like this

completely balanced would looks like this:

# 解答2[Java]：非递归，深度优先遍历

## 复杂度分析

• Time complexity : $O(N)$.
• Space complexity : $O(N)$.

# 解答3[Java]：非递归，广度优先遍历

## 复杂度分析

• Time complexity : $O(N)$.
• Space complexity : $O(N)$.

# LinkedList 类的相关方法

## add(E e)

Appends the specified element to the end of this list.

## poll()

Retrieves and removes the head (first element) of this list.

## pollLast()

Retrieves and removes the last element of this list, or returns null if this list is empty.

## 参考文献

LinkedList (Java Platform SE 8 )