《剑指offer》—— 23. 二叉搜索树的后续遍历序列（Java）
推荐
完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
}
}
思路：
先回顾了解一下二叉搜索树：
二叉搜索树（Binary Search Tree），（又：二叉查找树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
列如：
我们写一下上面这个二叉搜索树的后续遍历(左右根)：
2，5，3，8，7，6
根据后续遍历规则以及二叉搜索树的规则，我们可以知道：
- 最后一个元素是根节点；
- 比最后一个元素大的，是树的右子树的元素；比最后一个树小的，是树的左子树的元素；
综上，我们可以将树划分成 [2，5，3] [8，7] [6]
其中 [6]是根结点， [2，5，3] 是左子树的后续遍历， [8，7] 是右子树的后续遍历。
我们可以将划分出来的 左子树 和 右子树 再继续按照上述方法划分；
一直到将元素划分完，划分过程中，如果没有违反二叉搜索树的规则，就说明改后续遍历是某二叉搜索树的后续遍历。
实现：
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length == 0)
return false;
return check(sequence,0,sequence.length - 1);
}
private boolean check(int[] sequence, int first, int last){
if (last - first <= 1)
return true;
int rootVal = sequence[last];
int cutIndex = first;
while (cutIndex < last && sequence[cutIndex] <= rootVal)
cutIndex++;
for (int i = cutIndex; i < last; i ++)
if (sequence[i] < rootVal)
return false;
return check(sequence,first,cutIndex - 1) && check(sequence,cutIndex,last -1);
}
}
看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。
这里是猿兄，为你分享程序员的世界。
非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！
注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！
