-
Notifications
You must be signed in to change notification settings - Fork 67
/
Interview-7.md
146 lines (112 loc) · 5.6 KB
/
Interview-7.md
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
## Inverview-7：重建二叉树
**题目**：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入前序遍历序列{1,2,4, 7,3,5, 6, 8}和中序遍历序列{4, 7,2,1,5,3,8, 6}，则重建如下图所示的二叉树并输出它的头节点。
**前序遍历**：访问顺序为根节点、左子节点、右子节点。
**中序遍历**：访问顺序为左子节点、根节点、右子节点。
**后序遍历**：访问顺序为左子节点、右子节点、根节点。
根据前序遍历的特点，第一个数必定是根节点，根据中序遍历的特点，只要找到序列当中的根节点，在根节点的左边序列是左子树，在根节点的右边序列是右子树。
1. 创建一个二叉树类。
2. 编写递归函数，先写出满足最小分割的序列，也就是说如果前序遍历序列和中序遍历序列只有两个数值的时候，那么就可以得到叶子节点，并返回这个只有两层的子二叉树。
3. 如果分割的序列不只是两个数值，那么就需要继续分割子序列，递归调用，直到分割为只有两个数值为止。
4. 这也有特殊情况，也就是根节点在最后边、最左边或者是根节点的右边只有一个数值、根节点的左边只有一个数值，那么就可以构造叶子节点了。
5. 最后依次返回得到这颗二叉树。
```python
## 创建二叉树类
class Node():
def __init__(self, item):
self.element = item
self.leftNode = None
self.rightNode = None
## 构建二叉树
def struct_tree(pre_list, middle_list):
if len(pre_list) == 2:
# 根节点
node = Node(pre_list[0])
#左叶子节点
if pre_list[0] == middle_list[1]:
left_node = Node(pre_list[1])
node.leftNode = left_node
else:
# 右叶子节点
right_node = Node(pre_list[1])
node.rightNode = right_node
## 添加父节点
if node.leftNode != None:
node.leftNode.parentNode = node
if node.rightNode != None:
node.rightNode.parentNode = node
return node
else:
## 递归调用
for i in range(len(middle_list)):
if middle_list[i] == pre_list[0]:
middle_root_index = i
# 根节点
node = Node(pre_list[0])
# 左子树
if middle_root_index > 1:
left_pre_list = pre_list[1 : middle_root_index + 1]
left_middle_list = middle_list[0 : middle_root_index]
node.leftNode = struct_tree(left_pre_list, left_middle_list)
elif middle_root_index == 1:
left_node = Node(middle_list[0])
node.leftNode = left_node
# 右子树
if middle_root_index < len(pre_list) - 2:
right_pre_list = pre_list[middle_root_index + 1 : ]
right_middle_list = middle_list[middle_root_index + 1 : ]
node.rightNode = struct_tree(right_pre_list, right_middle_list)
elif middle_root_index == len(pre_list) - 2:
right_node = Node(middle_list[len(pre_list) - 1])
node.rightNode = right_node
## 添加父节点
if node.leftNode != None:
node.leftNode.parentNode = node
if node.rightNode != None:
node.rightNode.parentNode = node
return node
pre_list = [1, 2, 4, 7, 3, 5, 6, 8]
middle_list = [4, 7, 2, 1, 5, 3, 8, 6]
node = struct_tree(pre_list, middle_list)
print('根节点：', node.element)
```
根节点： 1
**Inverview-7测试用例**
```python
## 完全二叉树
pre_list = [1, 2, 4, 8, 9, 5, 10, 3, 6, 7]
middle_list = [8, 4, 9, 2, 10, 5, 1, 6, 3, 7]
node = struct_tree(pre_list, middle_list)
print('最左边的叶子节点：', node.leftNode.leftNode.leftNode)
## 不完全二叉树
pre_list = [1, 2, 4, 8, 9, 5, 10, 3, 7]
middle_list = [8, 4, 9, 2, 10, 5, 1, 3, 7]
node = struct_tree(pre_list, middle_list)
print('最右边的叶子节点：', node.rightNode.rightNode)
## 所有节点都没有右子节点的二叉树
pre_list = [1, 2, 4, 8]
middle_list = [8, 4, 2, 1]
node = struct_tree(pre_list, middle_list)
print('最左边的叶子节点：', node.leftNode.leftNode.leftNode)
## 所有节点都没有左子节点的二叉树
pre_list = [1, 3, 7]
middle_list = [1, 3, 7]
node = struct_tree(pre_list, middle_list)
print('最右边的叶子节点：', node.rightNode.rightNode)
## 只有1个节点的二叉树
pre_list = [1]
middle_list = [1]
node = struct_tree(pre_list, middle_list)
print('根节点：', node.element)
```
最左边的叶子节点： 8
最右边的叶子节点： 7
最左边的叶子节点： 8
最右边的叶子节点： 7
根节点： 1
> 作者：[@mantchs](https://github.com/NLP-LOVE/ML-NLP)
>
> GitHub：[https://github.com/NLP-LOVE/CodingInterviews2-ByPython](https://github.com/NLP-LOVE/CodingInterviews2-ByPython)
>
> 有意向一起完成此项目或者有问题、有补充的可以加入《剑指offer》讨论群【818185620】<a target="_blank" href="//shang.qq.com/wpa/qunwpa?idkey=8c188e86e0eac4a214861c2c706a9c0baf75176e16e52f07b8a64d1a13f99a0d"><img border="0" src="http://pub.idqqimg.com/wpa/images/group.png" alt="《剑指offer》讨论群" title="《剑指offer》讨论群"></a>