• 二叉搜索树的后序遍历序列
    • 题目
    • 解题思路

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

    题目

    牛客网

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出 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. }
    5. if (sequence.length == 1) {
    6. return true;
    7. }
    8. return isBST(sequence, 0, sequence.length - 1);
    9. }
    10. private boolean isBST(int[] sequence, int start, int end) {
    11. if (start < 0 || end < 0 || start >= end) {
    12. return true;
    13. }
    14. int rootV = sequence[end];
    15. int rightIndex = -1, rightV = Integer.MIN_VALUE;
    16. for (int i = start; i < end; i++) {
    17. if (rightV == Integer.MIN_VALUE && sequence[i] > rootV) {
    18. rightV = sequence[i];
    19. rightIndex = i;
    20. continue;
    21. }
    22. if (rightV != Integer.MIN_VALUE && sequence[i] < rootV) {
    23. return false;
    24. }
    25. }
    26. return isBST(sequence, start, rightIndex - 1) && isBST(sequence, rightIndex, end - 1);
    27. }