/
main.c
95 lines (80 loc) · 2.75 KB
/
main.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
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
#include <stdio.h>
struct TreeLinkNode {
int val;
struct TreeLinkNode *left, *right, *next;
};
/**
* 填充二叉树的next指针
*/
void connect(struct TreeLinkNode *root) {
int height(struct TreeLinkNode *);
struct TreeLinkNode* findLeftestNode(struct TreeLinkNode *, int);
struct TreeLinkNode* findRightestNode(struct TreeLinkNode *, int);
if (root == NULL) return;
/* 获取左右子树高度 */
int heightLeft = height(root->left);
int heightRight = height(root->right);
// 确定当前需要connect的左右子树的层数
int i = 1, end = heightLeft < heightRight ? heightLeft : heightRight;
/* 连接每一层,左子树的最右结点next指针指向右子树最左结点 */
struct TreeLinkNode *left, *right;
while (i <= end) {
left = findRightestNode(root->left, i);
right = findLeftestNode(root->right, i);
left->next = right;
++i;
}
/* 递归填充处理左右子树 */
connect(root->left);
connect(root->right);
}
/**
* 获取二叉树高度
*/
int height(struct TreeLinkNode *root) {
int bigger(int, int);
if (root == NULL) return 0;
return bigger(height(root->left), height(root->right)) + 1;
}
/** 获取两者中的较大数 */
int bigger(int param1, int param2) { return param1 > param2 ? param1 : param2; }
/**
* 寻找root下某一层最左侧的结点
*/
struct TreeLinkNode* findLeftestNode(struct TreeLinkNode *root, int level) {
int height(struct TreeLinkNode *);
if (level == 1) return root;
if (height(root->left) >= level - 1)
return findLeftestNode(root->left, level - 1);
else
return findLeftestNode(root->right, level - 1);
}
/**
* 寻找root下某一层最右侧的结点
*/
struct TreeLinkNode* findRightestNode(struct TreeLinkNode *root, int level) {
int height(struct TreeLinkNode *);
if (level == 1) return root;
if (height(root->right) >= level - 1)
return findRightestNode(root->right, level - 1);
else
return findRightestNode(root->left, level - 1);
}
void print(struct TreeLinkNode *root) {
if (root == NULL) return;
if (root->next == NULL) printf("%d->null\n", root->val);
else printf("%d->%d\n", root->val, root->next->val);
print(root->left);
print(root->right);
}
int main() {
struct TreeLinkNode n1, n2, n3, n4, n5, n7;
n1.val = 1; n1.left = &n2; n1.right = &n3; n1.next = NULL;
n2.val = 2; n2.left = &n4; n2.right = &n5; n2.next = NULL;
n3.val = 3; n3.left = NULL; n3.right = &n7; n3.next = NULL;
n4.val = 4; n4.left = NULL; n4.right = NULL; n4.next = NULL;
n5.val = 5; n5.left = NULL; n5.right = NULL; n5.next = NULL;
n7.val = 7; n7.left = NULL; n7.right = NULL; n7.next = NULL;
connect(&n1);
print(&n1);
}