剑指offer(12)-二叉搜索树的后序遍历序列[数据结构]九度1367 | Acm之家
Read full article from 剑指offer(12)-二叉搜索树的后序遍历序列[数据结构]九度1367 | Acm之家
- 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
- 输入：
- 每个测试案例包括2行：第一行为1个整数n(1<=n<=10000)，表示数组的长度。
第二行包含n个整数，表示这个数组，数组中的数的范围是[0,100000000]。
- 输出：
- 对应每个测试案例，如果输入数组是某二叉搜索树的后序遍历的结果输出Yes，否则输出No。
以 5 7 6 9 11 10 8 为例： 根节点为8，左子树为 5 7 6 又子树为 11 10。
所以，任务就是先找到左子树。
程序中是这样找的：
int k = start; //k为右子树的开始位置(左子树都是比根节点小的数)
while(arr[k] < arr[end] && k <= end-1) k++;
while(arr[k] < arr[end] && k <= end-1) k++;
此时，arr[k] == 11。即右子树开始的位置。 接下来判断右子树是否是符合要求的，即都比根节点大。
10 | bool check(int start, int end){ |
11 | //任意3个或3个以下的数都符合 |
12 | if(start >= end-2) return true; |
13 | int k = start; //k为右子树的开始位置(左子树都是比根节点小的数) |
14 | while(arr[k] < arr[end] && k <= end-1) k++; |
15 | j = k; |
16 | //只要右子树中有比根节点小的就不符合 |
17 | while(j < end) if(arr[j++] < arr[end]) return false; |
18 | return check(start,k-1) && check(k,end-1); //分别判断左右子树 |
19 | } |
