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

发表于2020-07-08更新于2020-07-08

在线测评地址：牛客网

题目描述

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

思路

二叉搜索树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

解题思路：后序遍历 的序列中，最后一个数字是树的根节点 ，数组中前面的数字可以分为两部分：第一部分是左子树节点 的值，都比根节点的值小；第二部分 是右子树 节点的值，都比 根 节点 的值大，后面用递归分别判断前后两部分 是否 符合以上原则

编程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function VerifySquenceOfBST(sequence, start=0, end=sequence.length - 1)
{
    if (sequence.length === 0) {
        return false
    }
    if (start >= end) {
        return true
    }
    for (var i = start; i < end; i++) {
        if (sequence[i] > sequence[end]) {
            break
        }
    }
    for (var j = i + 1; j < end; j++) {
        if (sequence[j] < sequence[end]) {
            return false
        }
    }

    return VerifySquenceOfBST(sequence, start, i - 1) && VerifySquenceOfBST(sequence, i, end - 1)
}