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
| import Foundation
class For06Solution {
func rebuildTree1(_ preOrder: [Int], _ inOrder: [Int] ) -> TreeNode? {
var p = preOrder
var i = inOrder
return recursive2(&p, &i, 0, i.count-1)
//下面是循环
var rootValue = preOrder[0]
var tree = TreeNode(rootValue)
let res = tree
var rightTree = tree
//左子树长度
var leftLen = 0
while inOrder[leftLen] != rootValue {
leftLen += 1
}
for (i , n) in preOrder.enumerated() {
var findIndex = 0
if i == 0 {
continue
}else if i <= leftLen {
findIndex = 0
while findIndex <= leftLen {
//从左向右查找，先找到根节点，说明n在右子树上
if inOrder[findIndex] == rootValue {
tree.right = TreeNode(n)
tree = tree.right!
rootValue = n
break
}else if inOrder[findIndex] == n {
tree.left = TreeNode(n)
tree = tree.left!
rootValue = n
break
}
findIndex += 1
}
}else {
findIndex = leftLen + 1
let rightLen = preOrder.count - 1
if findIndex == i {
//右子树的第一个节点
rootValue = n
}
while findIndex <= rightLen {
if inOrder[findIndex] == rootValue {
rightTree.right = TreeNode(n)
rightTree = rightTree.right!
rootValue = n
break
}else if inOrder[findIndex] == n {
rightTree.left = TreeNode(n)
rightTree = rightTree.left!
rootValue = n
break
}
findIndex += 1
}
}
}
return res
}
//不能改变输入
func recursive1(_ preOrder: inout [Int],_ startPre: Int,_ endPre: Int, _ inOrder: inout [Int],_ startIn: Int,_ endIn: Int) -> TreeNode? {
if startPre > endPre || startIn > endIn {
return nil
}
let root = TreeNode(preOrder[startPre])
print(root.val)
for index in startIn...endIn {
if inOrder[index] == root.val {
root.left = recursive1(&preOrder, startPre+1, startPre+(index-startIn), &inOrder, startIn, index-1)
root.right = recursive1(&preOrder, startPre+(index-startIn)+1, endPre, &inOrder, index+1, endIn)
break
}
}
return root
}
//能改变输入
func recursive2(_ preOrder: inout [Int], _ inOrder: inout [Int],_ startIn: Int,_ endIn: Int) -> TreeNode? {
if preOrder.count == 0 || startIn > endIn {
return nil
}
let root = TreeNode(preOrder.removeFirst())
print(root.val)
for index in startIn...endIn {
if inOrder[index] == root.val {
print("\(startIn)+++\(index)+++\(endIn)")
root.left = recursive2(&preOrder, &inOrder, startIn, index-1)
root.right = recursive2(&preOrder, &inOrder, index+1, endIn)
break
}
}
return root
}
}
|
