Problem solution 1008 “Construct Binary Search Tree from Preorder Traversal” from LeetCode.
Problem
Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
It’s guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.
example
1
2
|
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
|
Constraints
- 1 <=
preorder.length <= 100
- 1 <=
preorder[i] <= 10^8
- The values of preorder are distinct.
Solution
Add elements to BST
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
|
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func bstFromPreorder(preorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
root := TreeNode{
Val: preorder[0],
}
for idx:=1;idx<len(preorder);idx++ {
helper(&root, preorder[idx])
}
return &root
}
func helper(root *TreeNode, idx int) {
if idx<root.Val {
if root.Left == nil {
root.Left= &TreeNode{
Val: idx,
}
} else {
helper(root.Left, idx)
}
} else {
if root.Right == nil {
root.Right= &TreeNode{
Val: idx,
}
} else {
helper(root.Right, idx)
}
}
}
|
Reorder elements
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
|
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func bstFromPreorder(preorder []int) *TreeNode {
cur := 0
return helper(preorder, 0, 1<<31 - 1, &cur)
}
func helper(preorder []int, prev int, max int, cur *int) *TreeNode{
if len(preorder) == 0 {
return nil
}
if *cur == len(preorder) {
return nil
}
if preorder[*cur]> max {
return nil
}
root := &TreeNode {
Val: preorder[*cur],
}
*cur++
root.Left = helper(preorder, root.Val, root.Val, cur)
root.Right = helper(preorder, root.Val, max, cur)
return root
}
|