剑指的后遍历序列提供二进制搜索树

输入一个整数数组序列二叉排序树，以确定该数组是否是遍历二叉搜索树的结果. 如果是，则输出“是”，否则输出“否”. 假设输入数组中的任何两个数字互不相同.

分析: 如果数组是二进制搜索树的后遍历的结果，则该数组具有以下特征: 数组的最后一个元素是（子）树的根节点序列二叉排序树，前一个是部分可以分为两部分，前一部分的元素都小于最后一个元素的值，后一部分大于数组中最后一个元素的值，我们首先需要找到这个临界值，在判断前一部分的元素是否小于数组末尾的值，然后判断数组的前两个部分进行部分处理（递归定义）.

 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

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-236096-1.html