// 面试题33：二叉搜索树的后序遍历序列 // 题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。 // 如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。 #include <cstdio> // BST：Binary Search Tree，二叉搜索树 bool VerifySquenceOfBST(int sequence[], int length) { if (sequence == nullptr || length <= 0) return false; //当前根节点 int root = length - 1; //判断左子树节点 int i = 0; for (; i < length - 1; ++i) { if (sequence[i] > sequence[root]) break; } //判断右子树节点 int j = i; for (; j < length - 1; ++j) { if (sequence[j] < sequence[root]) return false; } //检查左子树 bool left = true; if (i > 0) left = VerifySquenceOfBST(sequence, i); //检查右子树 bool right = true; if (i < length - 1) right = VerifySquenceOfBST(sequence + i, length - i - 1); return (left && right); }
// ====================测试代码==================== void Test(const char* testName, int sequence[], int length, bool expected) { if (testName != nullptr) printf("%s begins: ", testName); if (VerifySquenceOfBST(sequence, length) == expected) printf("passed.\n"); else printf("failed.\n"); } // 10 // / // 6 14 // /\ /// 4 8 12 16 void Test1() { int data[] = { 4, 8, 6, 12, 16, 14, 10 }; Test("Test1", data, sizeof(data) / sizeof(int), true); } // 5 // / // 4 7 // / // 6 void Test2() { int data[] = { 4, 6, 7, 5 }; Test("Test2", data, sizeof(data) / sizeof(int), true); } // 5 // / // 4 // / // 3 // / // 2 // / // 1 void Test3() { int data[] = { 1, 2, 3, 4, 5 }; Test("Test3", data, sizeof(data) / sizeof(int), true); } // 1 // // 2 // // 3 // // 4 // // 5 void Test4() { int data[] = { 5, 4, 3, 2, 1 }; Test("Test4", data, sizeof(data) / sizeof(int), true); } // 树中只有1个结点 void Test5() { int data[] = { 5 }; Test("Test5", data, sizeof(data) / sizeof(int), true); } void Test6() { int data[] = { 7, 4, 6, 5 }; Test("Test6", data, sizeof(data) / sizeof(int), false); } void Test7() { int data[] = { 4, 6, 12, 8, 16, 14, 10 }; Test("Test7", data, sizeof(data) / sizeof(int), false); } void Test8() { Test("Test8", nullptr, 0, false); } int main(int argc, char* argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); Test7(); Test8(); return 0; }
分析：递归分析子树。
容器操作没有指针简单。
class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if (sequence.size() <= 0) return false; return Verify(sequence, 0, sequence.size() - 1); } bool Verify(vector<int>& sequence, int start, int end) { if (start >= end) return true; int root = sequence[end]; //判断左子树节点 int i = start; for (; i < end; ++i) if (sequence[i] > root) //当前节点值大于根节点跳出 break; //判断右子树节点 for (int j = i; j < end; ++j) if (sequence[j] < root) return false; return Verify(sequence, start, i - 1) && Verify(sequence, i, end - 1); } };
原文：https://www.cnblogs.com/ZSY-blog/p/12603423.html
