LintCode (97) Maximum Depth of Binary Tree Show result

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.

Have you met this question in a real interview? 

Yes

Example

Given a binary tree as follow:

  1
 / \ 
2   3
   / \
  4   5

The maximum depth is

基本上看到这种最大最小的，或者和traverse有点关系的，要门dfs, bfs,要么就是divide and conquer. 这题要是犯贱也可以写个traversal,维护一个最大深度。不过最好好事d&c吧。 那么一个公式，算算左边，算算右边，比较比较，得到结果。。。

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

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: An integer */ int maxDepth(TreeNode *root) { // write your code here if (!root) return 0; return max(maxDepth(root->left),maxDepth(root->right))+1; } };