-
Notifications
You must be signed in to change notification settings - Fork 0
/
buildTree.go
executable file
·89 lines (79 loc) · 2.11 KB
/
buildTree.go
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
package binaryTree
func buildTree(inorder []int, postorder []int) *TreeNode {
if len(inorder) == 0 || len(postorder) == 0 {
return nil
}
root := new(TreeNode)
if len(inorder) == 1 && len(postorder) == 1 {
root.Val = inorder[0]
return root
}
rootV := postorder[len(postorder)-1]
root.Val = rootV
rootindex := 0
for i := 0; i < len(inorder); i++ {
if inorder[i] == rootV {
rootindex = i
}
}
root.Left = buildTree(inorder[0:rootindex], postorder[0:rootindex])
root.Right = buildTree(inorder[rootindex+1:], postorder[rootindex:len(postorder)-1])
return root
}
//疑问: 二叉树节点上的值重复?
//func buildTree(inorder []int, postorder []int) *TreeNode {
// if len(inorder) == 0 || len(postorder) == 0 {
// return nil
// }
// root := new(TreeNode)
// if len(inorder) == 1 && len(postorder) == 1 {
// root.Val = inorder[0]
// return root
// }
//
// //Find root node in inorder
// rootindex := 0
// rootValue := postorder[len(postorder)-1]
// for i, v := range inorder {
// if v == rootValue {
// root.Val = v
// rootindex = i
// }
// }
//
// leftInorder := inorder[:rootindex]
// rightInorder := inorder[rootindex+1:]
// leftPostorder := postorder[:len(leftInorder)]
// rightPostorder := postorder[len(leftInorder) : len(postorder)-1]
//
// root.Left = buildTree(leftInorder, leftPostorder)
// root.Right = buildTree(rightInorder, rightPostorder)
//
// return root
//}
func buildTreePreAndInorder(preorder []int, inorder []int) *TreeNode {
if len(inorder) == 0 || len(preorder) == 0 {
return nil
}
root := new(TreeNode)
if len(inorder) == 1 && len(preorder) == 1 {
root.Val = inorder[0]
return root
}
//Find root node in inorder
rootindex := 0
rootValue := preorder[0]
for i, v := range inorder {
if v == rootValue {
root.Val = v
rootindex = i
}
}
leftInorder := inorder[:rootindex]
rightInorder := inorder[rootindex+1:]
leftPreorder := preorder[1 : len(leftInorder)+1]
rightPreorder := preorder[len(leftInorder)+1 : len(preorder)]
root.Left = buildTreePreAndInorder(leftPreorder, leftInorder)
root.Right = buildTreePreAndInorder(rightPreorder, rightInorder)
return root
}