1. 本题知识点

树

2. 题目描述

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

3. 解题思路

根据二叉搜索树的后序遍历结果，最后一个元素一定是树的根结点。
```
后序遍历结果：2436875那么根结点的值为：5
```

再次从头开始遍历，小于根结点的值为其左子树，直到第一个大于根结点的元素开始，都为其右子树。
```
根结点：5根结点左子树：243根结点右子树：687
```
如果其右子树的序列中有元素的值小于根结点，则说明这不是二叉搜索树，比如下面的情况：
```
根结点：5根结点左子树：243根结点右子树：617
```

再将左子树和右子树递归以上过程就行了。

4. 代码

public class Solution {
       public boolean VerifySquenceOfBST(int[] sequence) {
           if (sequence == null || sequence.length == 0) {
               return false;        }        return VerifySquenceOfBST(sequence, 0, sequence.length - 1);    }    public boolean VerifySquenceOfBST(int[] sequence, int start, int end) {
           if (start >= end) {
               return true;        }        int i;        for (i = start; i < end; i++) {
               // 当碰到第一个大于根结点的元素时，退出            if (sequence[i] > sequence[end]) {
                   break;            }        }        for (int j = i; j < end; j++) {
               // 如果其右子树的序列中有元素的值小于根结点，则说明这不是二叉搜索树            if (sequence[j] < sequence[end]) {
                   return false;            }        }        return VerifySquenceOfBST(sequence, start, i - 1) && VerifySquenceOfBST(sequence, i, end - 1);    }}

转载地址：http://ryjvb.baihongyu.com/

你可能感兴趣的文章