题目描述
二叉搜索树的后序遍历序列, GO实现
Go 代码
var seq []int
func dfs(l int, r int) bool {
if l >= r {
return true
}
var (
root = seq[r]
k = l
)
for seq[k] < root && k < r {
k += 1
}
for i := k; i < r; i += 1 {
if seq[i] < root {
return false
}
}
return dfs(l, k-1) && dfs(k, r-1)
}
func verifySequenceOfBST(sequence []int) bool {
seq = sequence
return dfs(0, len(seq)-1)
}