https://www.nowcoder.net/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

 

题目描述

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

 

思路：

我知道应该用最后一个数字来测试，但是觉得有点麻烦，就没有细想。

但是其实用递归，是可以很巧妙的。

在网上搜到的几个方法也都是用递归来做的。

 

代码：

class Solution {    vector
       
         sv;    bool verify(int b, int e) {        if (b >= e) return true;        int x = b;        for (; x
        
         = sv[e]) break;        }        for (int i=x; i
         

sequence) { // recursive sv = sequence; if (sv.size() == 0) return false; return verify(0, sv.size()-1); }};