当前位置:  首页>> 技术小册>> 数据结构与算法(下)

题目描述

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

解法

序列的最后一个元素是二叉搜索树的根节点。

在序列中从左到右找到根节点的左子树(比根节点小)、右子树(比根节点大)。

  • 如果右子树中出现比根节点小的元素,那么为 false。
  • 否则递归左右子树。
  1. /**
  2. * @author bingo
  3. * @since 2018/11/23
  4. */
  5. public class Solution {
  6. /**
  7. * 判断数组是否是某个二叉搜索树的后序遍历序列
  8. *
  9. * @param sequence 数组
  10. * @return 是否属于某二叉搜索树的后序遍历序列
  11. */
  12. public boolean VerifySquenceOfBST(int[] sequence) {
  13. if (sequence == null || sequence.length < 1) {
  14. return false;
  15. }
  16. return verify(sequence, 0, sequence.length - 1);
  17. }
  18. private boolean verify(int[] sequence, int start, int end) {
  19. if (start >= end) {
  20. return true;
  21. }
  22. int val = sequence[end];
  23. int i = start;
  24. for (; i <= end; ++i) {
  25. if (sequence[i] >= val) {
  26. break;
  27. }
  28. }
  29. for (int j = i; j < end; ++j) {
  30. if (sequence[j] < val) {
  31. return false;
  32. }
  33. }
  34. return verify(sequence, start, i - 1) && verify(sequence, i, end - 1);
  35. }
  36. }

测试用例

  1. 功能测试(输入的后序遍历序列对应一棵二叉树,包括完全二叉树、所有节点都没有左/右子树的二叉树、只有一个节点的二叉树;输入的后续遍历序列没有对应一棵二叉树);
  2. 特殊输入测试(后序遍历序列为空指针)。

该分类下的相关小册推荐: