二叉搜索樹(shù)的后序遍歷序列
題目描述
輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果与境。如果是則輸出Yes,否則輸出No验夯。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。
相關(guān)知識(shí)
二叉查找樹(shù)（Binary Search Tree）摔刁，（又：二叉搜索樹(shù)挥转，二叉排序樹(shù)）它或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)： 若它的左子樹(shù)不空共屈，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值绑谣； 若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值拗引； 它的左借宵、右子樹(shù)也分別為二叉排序樹(shù)。
思路
- 根據(jù)二叉搜索樹(shù)的特點(diǎn)矾削，序列的最后一個(gè)元素是根結(jié)點(diǎn)壤玫，其左子樹(shù)全都比根結(jié)點(diǎn)小，右子樹(shù)全都比根節(jié)點(diǎn)大怔软。
- 將根結(jié)點(diǎn)前面的數(shù)組分為左右連個(gè)部分垦细，左側(cè)部分都小，右側(cè)部分都大挡逼；
- 如果右側(cè)部分有比根節(jié)點(diǎn)小的元素，那么就不是后序遍歷腻豌，如此遞歸進(jìn)行家坎。
實(shí)現(xiàn)代碼
function adjustSequence(sequence, start, end) {
if (start >= end) {
return true;
}
var i = end;
while (i > start && sequence[i - 1] > sequence[end]) {
--i;
}
for (var j = i - 1; j >= start; --j) {
if (sequence[j] > sequence[end]) {
return false;
}
}
return adjustSequence(sequence, start, i - 1) && (adjustSequence(sequence, i, end - 1));
}
function VerifySquenceOfBST(sequence) {
if (!sequence.length) {
return false;
}
return adjustSequence(sequence, 0, sequence.length - 1);
}
