2021-06-12：已知一棵搜尋二叉樹上沒有重複值的節點，現在有一個

2021-06-12：已知一棵搜尋二叉樹上沒有重複值的節點，現在有一個數組arr，是這棵搜尋二叉樹先序遍歷的結果。請根據arr生成整棵樹並返回頭節點。

福大大答案2021-06-12：

先序遍歷+中序遍歷（搜尋樹）+不重複值=唯一的二叉樹。

解法一

自然智慧。第0位置為根節點，遍歷1~N-1位置，找到比0位置大的，那就是屬於根的右節點。時間複雜度是O（N**2）。

解法二

單調棧。時間複雜度是O（N）。

程式碼用golang編寫。程式碼如下：

package mainimport （ “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 }}

執行結果如下：