已知一棵搜索二叉树上没有重复值的节点，现在有一个数组arr，是这棵搜索二叉树先序遍历的结果。请根据arr生成整棵树并返回头节点。
先序遍历+中序遍历（搜索树）+不重复值=唯一的二叉树。
解法一
自然智慧。第0位置为根节点，遍历1~N-1位置，找到比0位置大的，那就是属于根的右节点。时间复杂度是O(N**2)。
解法二
单调栈。时间复杂度是O(N)。
代码用golang编写。代码如下：
package main
import (
"container/list"
"fmt"
)
func main() {
arr := []int{8, 5, 1, 7, 10, 12}
ret1 := bstFromPreorder1(arr)
fmt.Println("----自然智慧----")
printTree(ret1)
fmt.Println("")
fmt.Println("----单调栈----")
ret2 := bstFromPreorder2(arr)
printTree(ret2)
}
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func printTree(head *TreeNode) {
if head == nil {
return
}
queue := list.New()
queue.PushBack(head)
for queue.Len() > 0 {
before := queue.Front()
queue.Remove(before)
beforeNode := before.Value.(*TreeNode)
fmt.Print(beforeNode.Val, "\t")
if beforeNode.Left != nil {
queue.PushBack(beforeNode.Left)
}
if beforeNode.Right != nil {
queue.PushBack(beforeNode.Right)
}
}
}
func bstFromPreorder1(pre []int) *TreeNode {
return process1(pre, 0, len(pre))
}
func process1(pre []int, start int, endnot int) *TreeNode {
if start == endnot {
return nil
}
if start+1 == endnot {
return &TreeNode{Val: pre[start]}
}
i := start + 1
for ; i < endnot; i++ {
if pre[start] < pre[i] {
break
}
}
head := &TreeNode{Val: pre[start]}
head.Left = process1(pre, start+1, i)
head.Right = process1(pre, i, endnot)
return head
}
// 已经是时间复杂度最优的方法了，但是常数项还能优化
func bstFromPreorder2(pre []int) *TreeNode {
if len(pre) == 0 {
return nil
}
N := len(pre)
nearBig := make([]int, N)
for i := 0; i < N; i++ {
nearBig[i] = -1
}
stack := list.New()
for i := 0; i < N; i++ {
for stack.Len() > 0 && pre[stack.Back().Value.(int)] < pre[i] {
nearBig[stack.Back().Value.(int)] = i
stack.Remove(stack.Back())
}
stack.PushBack(i)
}
return process2(pre, 0, N-1, nearBig)
}
func process2(pre []int, L int, R int, nearBig []int) *TreeNode {
if L > R {
return nil
}
firstBig := twoSelectOne(nearBig[L] == -1 || nearBig[L] > R, R+1, nearBig[L])
head := &TreeNode{Val: pre[L]}
head.Left = process2(pre, L+1, firstBig-1, nearBig)
head.Right = process2(pre, firstBig, R, nearBig)
return head
}
func twoSelectOne(c bool, a int, b int) int {
if c {
return a
} else {
return b
}
}执行结果如下：
