[九度][何海涛] 二叉搜索树的后序遍历序列 - chkkch - 博客园

[九度][何海涛] 二叉搜索树的后序遍历序列 - chkkch - 博客园
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

由于BST的左半部分都小于根，右半部分都大于根，我们可以根据这条性质来判断。后续遍历的最后一个是根，所以先找出根，然后找出右半部分就是连续大于根的部分，然后再去判断左半部分有大于根的元素肯定就不符合了。然后递归判断左子树和右子树。
P.S. 如果给的是一棵中序遍历的BST呢？可能的解答就是先枚举根的位置枚举的同时判断左半部分和右半部分时候是否符合BST的性质。

bool check(int a[], int beg, int end)
 5 {
 6     if (beg > end)
 7         return true;
 8 
 9     int root = a[end];
10 
11     int mid = end - 1;
12 
13     while(mid >= beg)
14     {
15         if (a[mid] > root)
16             mid--;
17         else
18             break;
19     }
20 
21     for(int i = beg; i <= mid; i++)
22         if (a[i] > root)
23             return false;
24 
25     bool left = check(a, beg, mid);
26     bool right = check(a, mid + 1, end - 1);
27 
28     return left && right;
29 }

Read full article from [九度][何海涛] 二叉搜索树的后序遍历序列 - chkkch - 博客园