题目描述
从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉树，输出所有可能生成此树的数组。
示例:
给定如下二叉树
2
/ \
1 3
返回:
[
[2,1,3],
[2,3,1]
]
解法
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 | /* class TreeNode {
* var val: Int
* var left: TreeNode?
* var right: TreeNode?
*
* init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
* self.val = val
* self.left = left
* self.right = right
* }
* }
*/
class Solution {
func BSTSequences(_ root: TreeNode?) -> [[Int]] {
guard let root = root else { return [[]] }
var result = [[Int]]()
let prefix = [root.val]
let leftSeq = BSTSequences(root.left)
let rightSeq = BSTSequences(root.right)
for left in leftSeq {
for right in rightSeq {
var weaved = [[Int]]()
weaveLists(left, right, &weaved, prefix)
result.append(contentsOf: weaved)
}
}
return result
}
private func weaveLists(_ first: [Int], _ second: [Int], _ results: inout [[Int]], _ prefix: [Int]) {
if first.isEmpty || second.isEmpty {
var result = prefix
result.append(contentsOf: first)
result.append(contentsOf: second)
results.append(result)
return
}
var prefixWithFirst = prefix
prefixWithFirst.append(first.first!)
weaveLists(Array(first.dropFirst()), second, &results, prefixWithFirst)
var prefixWithSecond = prefix
prefixWithSecond.append(second.first!)
weaveLists(first, Array(second.dropFirst()), &results, prefixWithSecond)
}
}
|