二叉搜索樹的后續(xù)遍歷
題目描述：
輸入一個(gè)整數(shù)數(shù)組评疗，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果测砂。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同百匆。
解題思路：
- 根據(jù)后續(xù)遍歷的特點(diǎn)砌些，每次遍歷到根結(jié)點(diǎn)的時(shí)候都是最后一位
- 而二叉搜索樹的特點(diǎn)就是左子樹都小于等于root，右子樹都大于等于root
- 所以加匈，先找到根結(jié)點(diǎn)存璃，然后由前向后遍歷該序列
- 開始的部分的數(shù)值應(yīng)該都是小于等于root的（左子樹），當(dāng)某個(gè)結(jié)點(diǎn)大于root的值的時(shí)候矩动，此結(jié)點(diǎn)開始就是右子樹
- 遍歷右子樹的所有數(shù)值（后序遍歷的中后段）有巧，如果有數(shù)值小于root，則說(shuō)明該序列不是后續(xù)遍歷序列
- 遞歸地判斷做子樹和右子樹悲没，如果左右子樹也都是滿足后續(xù)遍歷的特點(diǎn)，那么整個(gè)序列就都滿足后續(xù)遍歷的特點(diǎn)男图。
代碼：
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if (sequence.empty()) {
return false;
}
int length = sequence.size();
int root = sequence[length - 1];
// 從前向后遍歷sequence序列
int i = 0;
for (; i < length - 1; ++i) {
if (sequence[i] > root)
break;
}
// 用另外一個(gè)變量來(lái)記錄右子樹開始的地方
int j = i;
// 遍歷右子樹示姿，如果右子樹中有元素小于root，則返回false
for (; j < length - 1; j++) {
if (sequence[j] < root) {
return false;
}
}
bool left = true;
bool right = true;
vector<int> leftSeq, rightSeq;
for (int count = 0; count < i; ++count) {
leftSeq.push_back(sequence[count]);
}
for (int count = i; count < length - 1; ++count) {
rightSeq.push_back(sequence[count]);
}
// 如果左子樹不是空樹逊笆，即左子樹的結(jié)尾結(jié)點(diǎn)大于0
// 遞歸驗(yàn)證左半子樹
if (i > 0) {
left = VerifySquenceOfBST(leftSeq);
}
// 如果右子樹不是空樹
// 遞歸驗(yàn)證右半子樹
if (i < length - 1) {
right = VerifySquenceOfBST(rightSeq);
}
return left && right;
}
};
2018.10.12
