http://www.geeksforgeeks.org/diameter-of-a-binary-tree/
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
using
namespace
std;
7
8
struct
node {
9
int
data;
10
struct
node *left, *
right;
11
node() : data(
0
), left(NULL), right(NULL) { }
12
node(
int
d) : data(d), left(NULL), right(NULL) { }
13
};
14
15
void
print(node *
node) {
16
if
(!node)
return
;
17
print(node->
left);
18
cout << node->data <<
"
"
;
19
print(node->
right);
20
}
21
22
int
diameter(node *root,
int
&
ans) {
23
if
(!root)
return
0
;
24
int
l = diameter(root->
left, ans);
25
int
r = diameter(root->
right, ans);
26
ans = max(ans, l+r+
1
);
27
return
max(l, r) +
1
;
28
}
29
30
31
int
main() {
32
struct
node* root =
new
node(
1
);
33
root->left =
new
node(
2
);
34
root->right =
new
node(
3
);
35
root->left->left =
new
node(
4
);
36
root->left->right =
new
node(
5
);
37
int
ans =
0
;
38
diameter(root, ans);
39
cout << ans <<
endl;
40
return
0
;
41
}
