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],

    3
/ \
9  20
/  \
15   7


return its depth = 3.

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

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
import java.lang.Math;
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int left_height = maxDepth(root.left);
int right_height = maxDepth(root.right);
return Math.max(left_height, right_height) + 1;
}
}
}


## 复杂度分析

• 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

    3
\
20
\
7
\
9
\
15


completely balanced would looks like this:

        3
/     \
9       20
/ \     /  \
8   4   15   7


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

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
import javafx.util.Pair;
import java.lang.Math;
class Solution {
public int maxDepth(TreeNode root) {
if (root != null) {
}

int depth = 0;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.pollLast();
root = current.getKey();
int current_depth = current.getValue();
if (root != null) {
depth = Math.max(depth, current_depth);
stack.add(new Pair(root.left, current_depth + 1));
stack.add(new Pair(root.right, current_depth + 1));
}
}
return depth;
}
};


## 复杂度分析

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

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

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
import java.util.Queue;
public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
int depth = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
depth++;
}

return depth;
}
}


## 复杂度分析

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