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.
同Minimum Depth of Binary Tree求解类似。 http://qiaopeng688.blog.51cto.com/3572484/1835237
代码如下:
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class
Solution {
public
:
int
maxDepth(TreeNode* root) {
int
iMaxDepth = 0;
vector<
int
> depths;
stack<TreeNode *> s;
TreeNode *p,*q;
q = NULL;
p = root;
if
(!root)
return
0;
while
(p != NULL || s.size() > 0)
{
while
( p != NULL)
{
s.push(p);
p = p->left;
}
if
(s.size() > 0)
{
p = s.top();
if
( NULL == p->left && NULL == p->right)
{
if
(iMaxDepth < s.size())
iMaxDepth = s.size();
}
if
( (NULL == p->right || p->right == q) )
{
q = p;
s.pop();
p = NULL;
}
else
p = p->right;
}
}
return
iMaxDepth;
}
};
|
本文转自313119992 51CTO博客,原文链接:http://blog.51cto.com/qiaopeng688/1835318