# 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:

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:

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.