题解 | #二叉搜索树的后序遍历序列#
对于二插搜索树BST的后续遍历正确合法序列,必须满足对于一个序列,最后一个元素x一定是根, 然后如果去掉最后一个元素得到的新的序列为T,那么T就满足:T可以分成两段,前一段为左子树 小于x,后一段右子树大于x,且这两段(子树)也必须是合法的搜索树后续遍历序列
function VerifySquenceOfBST(sequence)
{
// write code here
if(sequence.length == 0) return false
// 对于二插搜索树BST的后续遍历正确合法序列,必须满足对于一个序列,最后一个元素x一定是根,
// 然后如果去掉最后一个元素得到的新的序列为T,那么T就满足:T可以分成两段,前一段为左子树
// 小于x,后一段右子树大于x,且这两段(子树)也必须是合法的搜索树后续遍历序列
return judgeBST(0, sequence.length - 1)
function judgeBST(start, end){
if(start >= end){
// 子树遍历结束,说明此子序列符合BST二叉树后续遍历序列
return true
}
// 先找出第一个比sequence[end]大的元素索引
let index = end
for(let i = start; i < end; i++){
if(sequence[i] > sequence[end]){
index = i
console.log(index)
break
}
}
// 然后判断后面那一段子序列是否都比sequence[end]大,如果一旦有一个比它小,则它就不是一个后续遍历序列,直接返回false
for(let i = index + 1; i < end; i++){
if(sequence[i] < sequence[end]){
return false
}
}
// 如果满足以上条件,则就需要递归查找并判断sequence[end]为根节点的左右子树
return judgeBST(start, index-1) && judgeBST(index, end - 1)
}
}
module.exports = {
VerifySquenceOfBST : VerifySquenceOfBST
};