【IT笔试面试题整理】重建二叉树

【试题描述】输入二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设遍历结果中都不包含重复数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6},则重建出该二叉树,并以后续遍历输出。

【参考代码】

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
#include <iostream>
using namespace std;

struct BinaryTreeNode
{
int value;
BinaryTreeNode* left;
BinaryTreeNode* right;
};

BinaryTreeNode* rebulidBinaryTreeCore(int* startPreOrder, int* endPreOrder,
int* startInOrder, int* endInOrder) {

//先序遍历的第一个节点为根节点
//创建根节点
BinaryTreeNode* rootNode = new BinaryTreeNode();
rootNode->value = startPreOrder[0];
rootNode->left = NULL;
rootNode->right = NULL;

if(startPreOrder == endPreOrder) {
if(startInOrder == endInOrder
&& *startPreOrder == *startInOrder) {
return rootNode;
} else {
throw ("Invalid input.");
}
}

//在中序查找根节点
int* rootIndex = startInOrder;
while(rootIndex <= endInOrder && *rootIndex != rootNode->value) {
rootIndex++;
}
if(rootIndex == endInOrder && *rootIndex != rootNode->value) {
throw ("Invalid input.");
}

//重建左子树
int leftTreeLength = rootIndex - startInOrder;
if(leftTreeLength > 0) {
rootNode->left = rebulidBinaryTreeCore(startPreOrder + 1,
startPreOrder + leftTreeLength,
startInOrder,
rootIndex - 1);
}

//重建右子树
if(leftTreeLength < endPreOrder - startPreOrder) {
rootNode->right = rebulidBinaryTreeCore(startPreOrder + leftTreeLength + 1,
endPreOrder,
rootIndex + 1,
endInOrder);
}

return rootNode;
}

BinaryTreeNode* rebulidBinaryTree(int* preOrder, int* inOrder, int n) {
if(preOrder == NULL || inOrder == NULL || n <= 0) {
return NULL;
}

return rebulidBinaryTreeCore(preOrder, preOrder + n -1,
inOrder, inOrder + n - 1);
}

void printPostOrder(BinaryTreeNode* root) {
if(root!= NULL) {
if(root->left != NULL) {
printPostOrder(root->left);
}
if(root->right != NULL) {
printPostOrder(root->right);
}
cout << root->value << " ";
}
return ;
}

int main() {
int preOrder[8] = {1,2,4,7,3,5,6,8};
int inOrder[8] = {4,7,2,1,5,3,8,6};
BinaryTreeNode* root = rebulidBinaryTree(preOrder, inOrder, 8);
printPostOrder(root);
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!