# leetcode: Maximum Depth of Binary Tree

#### Problem Description:

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.

#### Solution and **Precautions**:

Way1: DFS to traverse the whole tree and use a variable to keep the current maximum depth, when encountering a deeper one, update the maximum depth. The accepted code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
void dfs(TreeNode *root, int depth, int *pmaxDepth) {
if (NULL == root->left && NULL == root->right)
*pmaxDepth = (depth > *pmaxDepth) ? depth : *pmaxDepth;
if (root->left) dfs(root->left, depth + 1, pmaxDepth);
if (root->right) dfs(root->right, depth + 1, pmaxDepth);
}
int maxDepthInner2(TreeNode *root) {
if (NULL == root) return 0;
int maxDepth = 0;
dfs(root, 1, &maxDepth);
return maxDepth;
}
int maxDepth(TreeNode *root) {
return maxDepthInner2(root);
}
};

Way 2: Or maybe a simpler way is just use recursive method without the explicit depth variable:

1
2
3
4
5
6
7

class Solution {
public:
int maxDepth(TreeNode *root) {
if (NULL == root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
};

#### Tips and Divergent thinking:

(1) The above simple code of Way 2 works efficiently because it is a tree rather than a graph, so we don’t have to manually keep some explicit intermediate depth variable as in DP.

(2) The code of Way 1 looks more tedious than that of way 2, however it is more generalized, we can easily modify the code to deal with other thing when we reach a leaf node, such as finding the minimum depth of binary tree! This cannot be easily done by simply modifying the code in Way 1.