我好久沒(méi)更新了 原因是我登不上賬號(hào)了..
題目：
輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果愈捅。如果是則返回true,否則返回false。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同叠殷。
例子：
輸入: [4,8,6,12,16,14,10]
輸出： true
我其實(shí)對(duì)后序遍歷的規(guī)律已經(jīng)不記得了 所以看了一下題解 大佬們總結(jié)的好到位：
二叉搜索樹(shù)的后序遍歷判斷：
1改鲫、首先明白二叉搜索樹(shù)的特點(diǎn)，左節(jié)點(diǎn)小于根林束，右節(jié)點(diǎn)大于根像棘，左右子樹(shù)也同樣是二叉搜索樹(shù)
2、根據(jù)二叉搜索樹(shù)的特點(diǎn)壶冒，我們發(fā)現(xiàn)需要遞歸的判斷缕题，根節(jié)點(diǎn)肯定在數(shù)組的末尾
3、找出比根節(jié)點(diǎn)小的就是左子樹(shù)胖腾，找到比根節(jié)點(diǎn)大的就是右子樹(shù)
4烟零、如果左右子樹(shù)中有不滿足的條件的元素則返回或者結(jié)束判斷
5、直到所有元素都判斷完則滿足二叉搜索樹(shù)的特點(diǎn)咸作，或者中途返回
根據(jù)大佬們總結(jié)的規(guī)律 我用JS實(shí)現(xiàn)了出來(lái)
function VerifySquenceOfBST(sequence)
{
// write code here
if(sequence.length === 0) {
return false
}
if(sequence.length === 1) {
return true
}
var root = sequence[sequence.length - 1]
var i = 0
//找到第一個(gè)大于根節(jié)點(diǎn)的節(jié)點(diǎn) 記錄好位置
while(sequence[i] < root) {
i++
}
//將原數(shù)組拆分成左子樹(shù)和右子樹(shù)
const leftarr = sequence.slice(0, i)
const rightarr = sequence.slice(i, sequence.length - 1)
//遍歷右子樹(shù) 如果有小于root的 則說(shuō)明不符合后序遍歷的規(guī)律
for(let a = 0; a <= rightarr.length - 1; a++) {
if(rightarr[a] < root) {
return false
}
}
// 將左子樹(shù)和右子樹(shù)放入該函數(shù)去查看是否符合后序遍歷規(guī)律 &結(jié)果即是最后的結(jié)果
return (leftarr.length === 0 ? true : VerifySquenceOfBST(leftarr)) && (rightarr.length === 0 ? true : VerifySquenceOfBST(rightarr))
}
