-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinaryTreeMaxLen.cpp
More file actions
126 lines (95 loc) · 2.8 KB
/
binaryTreeMaxLen.cpp
File metadata and controls
126 lines (95 loc) · 2.8 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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
//
// Created by mi on 12/11/17.
//
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef struct NODE {
struct NODE *pLeft; // 左子树
struct NODE *pRight; // 右子树
int nMaxLeft; // 左子树中的最长距离
int nMaxRight; // 右子树中的最长距离
char chValue; // 该节点的值
} NODE,*BTree;
struct NODEM{
NODEM *pLeft; // 左子树
NODEM *pRight; // 右子树
int nMaxLeft; // 左子树中的最长距离
int nMaxRight; // 右子树中的最长距离
char chValue; // 该节点的值
};
int nMaxLen = 0;
void FindMaxLen(NODE* root);
// 寻找树中最长的两段距离
void FindMaxLen(NODE *pRoot) {
// 遍历到叶子节点，返回
if (pRoot == NULL) {
return;
}
// 如果左子树为空，那么该节点的左边最长距离为0
if (pRoot->pLeft == NULL) {
pRoot->nMaxLeft = 0;
}
// 如果右子树为空，那么该节点的右边最长距离为0
if (pRoot->pRight == NULL) {
pRoot->nMaxRight = 0;
}
// 如果左子树不为空，递归寻找左子树最长距离
if (pRoot->pLeft != NULL) {
FindMaxLen(pRoot->pLeft);
}
// 如果右子树不为空，递归寻找右子树最长距离
if (pRoot->pRight != NULL) {
FindMaxLen(pRoot->pRight);
}
// 计算左子树最长节点距离
if (pRoot->pLeft != NULL) {
pRoot->nMaxLeft = ((pRoot->pLeft->nMaxLeft > pRoot->pLeft->nMaxRight) ? pRoot->pLeft->nMaxLeft
: pRoot->pLeft->nMaxRight) + 1;
}
// 计算右子树最长节点距离
if (pRoot->pRight != NULL) {
pRoot->nMaxRight = ((pRoot->pRight->nMaxLeft > pRoot->pRight->nMaxRight) ? pRoot->pRight->nMaxLeft
: pRoot->pRight->nMaxRight) + 1;
}
// 更新最长距离
if (pRoot->nMaxLeft + pRoot->nMaxRight > nMaxLen) {
nMaxLen = pRoot->nMaxLeft + pRoot->nMaxRight;
}
}
/*
int main(){
printf("niaho,binaryTreeMaxLen");
std::cout<<"\nniaho"<<endl;
BTree bTree;
bTree->chValue='g';
cout<<bTree->chValue<<endl;
*//*struct NODEM node1;
node1.chValue='g';
std::cout<<node1.chValue;
*//*
*//*
BNode node1;
node1.chValue='h';
cout<<node1.chValue<<endl;
*//*
//BNode *node1;
*//*
NODE *node2;
node1.chValue = 'u';
NODE *node3;
node1.chValue = 'o';
NODE *node4;
node1.chValue = 'h';
NODE *node5;
node1.chValue = 'a';
node1.pLeft=node2;
node1.pRight=node3;
node2->pLeft=node4;
node3->pRight=node5;
*//*
*//*
FindMaxLen(node1);
std::cout<<"nMaxLen:\t"<<nMaxLen;*//*
}*/