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

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

    题目

    牛客网

    输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出 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. }