二叉搜索树的后序遍历序列

题目

牛客网

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

解题思路

  1. 后序遍历中，最后一个节点为 root 节点
  2. 由于 BST 的左子树都小于 root，右子树都大于 root，那么可以判定该节点是否为 BST
  3. 依次类推，通过递归方式，再判定左右子树
  1. public boolean VerifySquenceOfBST(int[] sequence) {
  2.     if (sequence.length == 0) {
  3.         return false;
  4.     }
  6.     if (sequence.length == 1) {
  7.         return true;
  8.     }
  10.     return isBST(sequence, 0, sequence.length - 1);
  11. }
  13. private boolean isBST(int[] sequence, int start, int end) {
  14.     if (start < 0 || end < 0 || start >= end) {
  15.         return true;
  16.     }
  18.     int rootV = sequence[end];
  19.     int rightIndex = -1, rightV = Integer.MIN_VALUE;
  20.     for (int i = start; i < end; i++) {
  21.         if (rightV == Integer.MIN_VALUE && sequence[i] > rootV) {
  22.             rightV = sequence[i];
  23.             rightIndex = i;
  24.             continue;
  25.         }
  27.         if (rightV != Integer.MIN_VALUE && sequence[i] < rootV) {
  28.             return false;
  29.         }
  30.     }
  32.     return isBST(sequence, start, rightIndex - 1) && isBST(sequence, rightIndex, end - 1);
  33. }