剑指offer 二叉搜索树的后序遍历序列

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

分析：如果一个数组是一个二叉搜索树的后序遍历结果，那么这个数组有以下特征：数组的最后一个元素是（子）树的根节点，前面的部分可以分为两个部分，前一部分的元素都小于最后一个元素值，后一部分都大于数组最后一个元素值，我们首先需要找到这个临界值，在判断前一部分的元素是否都小于数组末尾的值，接着分别对数组前两部分处理，（递归定义）。

 1 class Solution {
 2     bool judge(vector<int> &sequence, int l, int r) {
 3         //如果l==r,即只有一个叶子节点，返回true，当l > r时空树，返回true
 4         if (l >= r) {
 5             return true;
 6         }
 7         int i = r - 1;
 8         //i指向第一个小于数组末尾值的元素下标
 9         while (i >= l && sequence[i] > sequence[r]) {
10             i--;
11         }
12         //判断前半部分所有元素值是否都小于数组末尾值
13         for (int j = i; j >= l; j--) {
14             if (sequence[j] > sequence[r]) {
15                 return false;
16             }
17         }
18         return judge(sequence, l, i) && judge(sequence, i + 1, r - 1);
19     }
20 public:
21     bool VerifySquenceOfBST(vector<int> sequence) {
22         int len = sequence.size();
23         if (len == 0) {
24             return false;
25         } else {
26             return judge(sequence, 0, len - 1);
27         }
28     }
29 };

2019.08.11

 1 class Solution {
 2 private:
 3     bool VerifySquenceOfBST(vector<int> sequence, int left, int right) {
 4         if (left >= right)
 5             return true;
 6         int i = left;
 7         int root = sequence[right];
 8         for (; i < right; i++) {
 9             if (sequence[i] > root)
10                 break;
11         }
12         int j = i;
13         for (; j < right; j++) {
14             if (sequence[j] < root)
15                 return false;
16         }
17         return VerifySquenceOfBST(sequence, left, i - 1) && VerifySquenceOfBST(sequence, i, right - 1);
18     }
19 public:
20     bool VerifySquenceOfBST(vector<int> sequence) {
21         int len = sequence.size();
22         if (len == 0) 
23             return false;
24         return VerifySquenceOfBST(sequence, 0, len - 1);
25     }
26 };