-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinTree_Longest_Path.cpp
More file actions
80 lines (76 loc) · 1.62 KB
/
BinTree_Longest_Path.cpp
File metadata and controls
80 lines (76 loc) · 1.62 KB
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
using namespace std;
typedef struct node
{
int value;
struct node *left;
struct node *right;
int maxlen_left;
int maxlen_right;
}BSTree,*pBSTree;
int nMaxlen=0;
void addBSNode(pBSTree &pCur,int x) //pCur is reference , value can be dynamic changed
{
if(NULL==pCur) //if tree node is null, create a new node and assigned to pCur,
{
pBSTree pNode=new BSTree();
pNode->left=NULL;
pNode->right=NULL;
pNode->value=x;
pNode->maxlen_left=0;
pNode->maxlen_right=0;
pCur=pNode;
}else
{
if(pCur->value>x)
addBSNode(pCur->left,x);
else if(pCur->value<x)
addBSNode(pCur->right,x);
else //not allow insert the same element
return;
}
}
void FindMaxlen(pBSTree pRoot)
{
if(pRoot==NULL)
return;
if(pRoot->left==NULL)
pRoot->maxlen_left=0;
if(pRoot->right==NULL)
pRoot->maxlen_right=0;
if(pRoot->left!=NULL)
FindMaxlen(pRoot->left);
if(pRoot->right!=NULL)
FindMaxlen(pRoot->right);
if(pRoot->left!=NULL)
{
int nTmplen=0;
if(pRoot->left->maxlen_left>pRoot->left->maxlen_right)
nTmplen=pRoot->left->maxlen_left;
else
nTmplen=pRoot->right->maxlen_right;
pRoot->maxlen_left=nTmplen+1;
}
if(pRoot->right!=NULL)
{
int nTmpMax=0;
if(pRoot->right->maxlen_left>pRoot->right->maxlen_right)
nTmpMax=pRoot->right->maxlen_left;
else
nTmpMax=pRoot->right->maxlen_right;
pRoot->maxlen_right=nTmpMax+1;
}
if(pRoot->maxlen_left+pRoot->maxlen_right>nMaxlen)
nMaxlen=pRoot->maxlen_left+pRoot->maxlen_right;
}
int main()
{
pBSTree pRoot=NULL;
int a[]={8,6,10,5,7,9,11};
int i=0;
for(i=0;i<7;i++)
addBSNode(pRoot,a[i]);
FindMaxlen(pRoot);
cout<<nMaxlen<<endl;
return 0;
}