大大普通 2023年12月22日上午11:44

c++
递归
class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
      if(postorder.size()==0)return true;
      int a=postorder[postorder.size()-1];
      vector<int>l,r;
      bool h=true;
      int i;
      for(i=0;i<postorder.size()-1;i++){
        if(postorder[i]<a&&h){
         l.push_back(postorder[i]);
        }
       else if(postorder[i]>a){
         r.push_back(postorder[i]);
         h=false;
        }
        else break;
      }
      if(i!=postorder.size()-1)return false;
      else return verifyTreeOrder(l)&&verifyTreeOrder(r);
      }
};

0 赞同 0 条回复

九号球普通 2023年11月18日上午10:19

“`java
后序遍历和二叉搜索树的定义，二叉搜索树要从左到右依次变大，后序遍历根节点在最后，小于根节点的是左子树，大于根节点的是右子树
class Solution {
public boolean verifyTreeOrder(int[] postorder) {
if (postorder == null) {
return true;
}
Stack stack = new Stack<>();
int root = Integer.MAX_VALUE;
for (int i = postorder.length – 1; i >= 0; i–) {
if (postorder[i] >= root) {
return false;
}
while (!stack.isEmpty() && stack.peek() > postorder[i]) {
root = stack.pop();
}
stack.add(postorder[i]);
}
return true;
}
}

0 赞同 0 条回复

招舟子普通 2023年8月26日下午3:23

class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postordernull){
return true;
}
return recur(postorder,0,postorder.length-1);
}
boolean recur(int[] postorder,int i,int j){
if(i>=j){
return true;
}
int n = i;
while(postorder[n]<postorder[j]){
n++;
}
for(int t=n;t<j;t++){
if(postorder[t]<postorder[j]){
return false;
}
}
return recur(postorder,i,n-1)&&recur(postorder,n,j-1);
}
}遍历

0 赞同 0 条回复

jhfuture 普通 2023年8月13日下午11:40

“`java
class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postorder==null) return true;

    return f(postorder,0,postorder.length-1);
}
boolean f(int[] postorder,int i,int j){
    if(i>=j){
        return true;
    }
    int root=postorder[j];
    int p=i;
    // 获取第一个大于root的
    while(postorder[p]<root) p++;
    // 从p处到j 进行判断，如果有小于的则返回FALSE；
    for(int k=p;k<j;k++){
        if(postorder[k]<root){
            return false;
        }
    }
    return f(postorder,i,p-1)&&f(postorder,p,j-1);

}

}
关键是理解分解子问题

0 赞同 0 条回复

CV大神普通 2023年7月20日上午9:57

class Solution {

    public boolean verifyPostorder(int[] postorder) {
        return isPostorder(postorder, 0, postorder.length - 1);
    }

    private boolean isPostorder(int[] postorder, int start, int end) {
        if(start >= end){
            return true;
        }
        int i = start;
        //会在进入右子树范围的时候不符合条件，因为右子树所有元素 > 根元素postorder[end]
        while (postorder[i] < postorder[end]){
            i++;
        }
        //因为已经进入了右子树范围，所以得-1才是左子树最后一个
        int leftTreeEnd = i - 1;
        //如果是二叉搜索树，肯定会在最后一个不满足条件，也就是postorder[i] == postorder[end]
        //此时i == end
        while (postorder[i] > postorder[end]){
            i++;
        }
        //所以这棵树是否正确，i == end
        return i ==end && isPostorder(postorder,start,leftTreeEnd) && isPostorder(postorder,leftTreeEnd+1,end -1);
    }
}

0 赞同 0 条回复

BOZ 普通 2023年7月11日上午11:33

【思路】递归实现。对于一个preoder序列，最后一位即根节点，从前往后遍历，找到第一个比根节点大的元素，即左右子树的分界点，而后可以进一步拆分问题进行递归。
【时间复杂度】最差O(n^2)
【空间复杂度】最差O(n)，即退化成链表

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        if (postorder.empty()) return true;

        function<bool(int,int)> _verifyPostorder = [&](int l, int r) -> bool {
            if (r - l < 2) return true;
            int median = postorder[r - 1]; int ridx = l;
            while(postorder[ridx] < median) ridx++;
            // printf("l = %d, r = %d, median = %d, ridx = %d\n", l, r, median, ridx);
            for (int i = ridx; i < r; i++)
                if (postorder[i] < median) return false;
            return _verifyPostorder(l, ridx) && _verifyPostorder(ridx, r - 1);
        };

        return _verifyPostorder(0, postorder.size());
    }
};

0 赞同 0 条回复

断舍离永久会员 2023年7月11日上午9:47

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null){
            return true;
        }

        return f(postorder,0,postorder.length-1);
    }

    public boolean f(int[] postorder, int left, int right){
        //说明正常走到遍历结束，返回true
        if(left >= right){
            return true;
        }
        //后序遍历数组的最后一个元素就是根节点
        int root = postorder[right];
        int flag = left;
        //获得第一个大于root的元素索引位置
        while (postorder[flag] < root){
            flag++;
        }
        //判断[flag, right-1]范围内是否存在比root小的元素,若存在则非法
        for(int i = flag; i < right; i++){
            if(postorder[i] < root){
                return false;
            }
        }
        //递归调用左右子树，需要都满足上面的判断
        return f(postorder,left, flag-1) && f(postorder,flag, right-1);
    }
}

0 赞同 0 条回复

憨憨永久会员 2023年7月10日下午12:09

通过递归每次找到第一个比当前节点大的节点，此节点就是左右子树的分割点，再从左右子树中查看是否符合搜索树，然后再对其子树再进行此操作

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder==null||postorder.length<=0){
            return true;
        }

        return f(postorder,0,postorder.length-1);

    }
    public boolean f(int[] postorder,int start,int end){
        if(start>=end){
            return true;
        }

        int root=postorder[end];

        int id=start;
        // for(int i=start;i<end;i++){
        //     if(root<postorder[i]){
        //         id=i;
        //         break;
        //     }
        // }
        while(postorder[id]<root)id++;

        for(int i=id;i<end;i++){
            if(root>postorder[i]){
                return false;
            }
        }

        return f(postorder,start,id-1)&&f(postorder,id,end-1);
    }

0 赞同 0 条回复

江畅普通 2023年7月8日下午11:44

// 二叉搜索树的后序遍历序列
// 时间复杂度 O(N^2)
// 空间复杂度 O(N)
class Solution {
private:
   // postorder: [........]
   //            [i. . . j] 
    bool check(vector<int>& postorder, int i, int j) {
        if (i >= j) { return true; }

        int root = postorder[j];

        // [i, ..., left) 左子树, 都小于 postorder[j]
        int left = i;
        while (left < j && postorder[left] < root) { ++left; }

        // [left, ..., j) 右子树, 都大于 postorder[j]
        for (int right = left; right < j; ++right) {
            if (postorder[right] < root) { return false; }
        }
        return check(postorder, i, left - 1) && check(postorder, left, j - 1);
    }
public:
    bool verifyPostorder(vector<int>& postorder) {
        return check(postorder, 0, postorder.size() - 1);
    }
};

0 赞同 0 条回复

Sexypig. 普通 2023年7月7日下午2:03

函数的目标是验证给定的后序遍历序列是否是一个二叉搜索树的后序遍历序列。
函数首先检查postorder数组的大小，如果为0，则返回true。
然后调用辅助函数check来进行验证。check函数接受三个参数，即postorder数组、左边界l和右边界r。
在check函数中，首先判断左边界是否大于等于右边界，如果是，则返回true。
然后，获取当前子树的根节点的值，即postorder[r]。
接下来，使用两个指针i和j来遍历数组。指针i从左边界开始，向右移动，直到找到第一个大于根节点值的元素。指针j从指针i的位置开始，向右移动，直到找到第一个小于根节点值的元素。
如果指针j没有达到右边界，则说明存在一个大于根节点值的元素，不满足二叉搜索树的性质，返回false。
最后，递归调用check函数来验证左子树和右子树是否满足二叉搜索树的性质，即调用check(postorder, l, i-1)和check(postorder, i, j-1)。
如果左子树和右子树都满足二叉搜索树的性质，则返回true，否则返回false。
整个函数的时间复杂度为O(nlogn)，其中n为数组postorder的长度。

#include<iostream>
#include<vector>

using namespace std;
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        if(postorder.size()==0) return true;
        return check(postorder,0,postorder.size()-1);
    }
    bool check(vector<int>& postorder,int l,int r) {
        if(l>=r) return true;
        int root=postorder[r];
        int i=l;
        while(i<r&&postorder[i]<root) ++i;
        int j=i;
        while(j<r&&postorder[j]>root) ++j;
        if(j<r) return false;
        return check(postorder,l,i-1)&&check(postorder,i,j-1);
    }
};

int main() {
    vector<int> postorder={1,2,5,10,6,9,4,3};
    Solution s;
    cout<<s.verifyPostorder(postorder);
    return 0;
}

0 赞同 0 条回复

残月冷骄阳普通 2023年7月5日下午1:59

复杂度

时间复杂度: $O(n^2)$
空间复杂度: $O(n)$

Code

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder,0,postorder.length-1);

    }
    boolean recur(int[] postorder,int i ,int j){
        if(i>=j){return true;}
        int p = i;
        while(postorder[p]<postorder[j]){p++;}
        int m = p;
        while(postorder[p]>postorder[j]){p++;}
        return p == j && recur(postorder,i,m-1)&& recur(postorder,m,j-1);
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月5日下午1:31

java
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        /* 二叉搜索树的特性和后序遍历结合足以确定父节点
           之后找到第一个比根小的节点和第一个比根大的节点作为左子树和右子树
           只要右子树中有节点比根节点小，返回false
           再递归检查左子树和右子树
        */
        if(postorder.length <= 1) {
            return true;
        }

        return f(postorder, 0, postorder.length - 1);
    }

    public boolean f(int[] postorder, int i, int j) {
        if(i >= j) {
            return true;
        }

        int parent = postorder[j];
        int p = i;
        //找到第一个大于父节点的元素
        while(postorder[p] < parent) {
            p ++;
        }

        for(int k = p + 1; k < j; k++) {
            if(postorder[k] < parent) {
                return false;
            }
        }

        return f(postorder, i, p-1) && f(postorder, p, j-1);
    }
}

时间和空间复杂度都是O(N)

0 赞同 0 条回复

局外人普通 2023年7月5日上午12:02

思路：同时结合二叉搜索树和后序遍历序列的性质，判断序列中每课子树是否为二叉树
时间复杂度O(n) 空间复杂度O(n)

class Solution {
    boolean check(int[] postorder, int low, int high){
        if(low>=high)   return true;

        int root = postorder[high];

        int left = low;
        while(left<high && postorder[left]<root)    left++;

        int right = left;
        while(right<high && postorder[right]>root)  right++;

        if(right!=high) return false;

        return check(postorder, low, left-1) && check(postorder, left, high-1);
    }
    public boolean verifyPostorder(int[] postorder) {
        return check(postorder, 0, postorder.length-1);
    }
}

0 赞同 0 条回复

WhyNot 普通 2023年7月4日下午3:22

bool verifyPostorder(int* postorder, int postorderSize) {
    if (postorder == NULL || postorderSize <= 0) {
        return true;
    }

    int root = postorder[postorderSize - 1];

    // 找到左子树的范围
    int i = 0;
    for (; i < postorderSize - 1; i++) {
        if (postorder[i] > root) {
            break;
        }
    }

    // 判断右子树中的元素是否都大于根节点
    int j = i;
    for (; j < postorderSize - 1; j++) {
        if (postorder[j] < root) {
            return false;
        }
    }

    // 递归判断左子树和右子树
    bool left = verifyPostorder(postorder, i);
    bool right = verifyPostorder(postorder + i, postorderSize - i - 1);

    return left && right;
}

时间复杂度为O(nlogn)
空间复杂度为O(logn)。

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午2:52

递归

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder,0,postorder.length-1);
    }
    public boolean recur(int[] postorder,int i,int j){
        if(i>=j)
            return true;
        int p=i;
        while(postorder[p]<postorder[j])
            p++;
        int m=p;
        while(postorder[p]>postorder[j])
            p++;
        return p==j&&recur(postorder,i,m-1)&&recur(postorder,m,j-1);
    }
}

0 赞同 0 条回复

彦，，# 普通 2023年7月4日上午11:11

// 递归
   bool verifyPostorder(vector<int>& postorder) {
    return recur(postorder, 0, postorder.size() - 1);
    }
    bool recur(vector<int>& postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }

0 赞同 0 条回复

屠龙手段普通 2023年7月3日下午9:01

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        return self.subTree(postorder, 0, len(postorder) - 1)

    def subTree(self, postorder, l, r):
        if l >= r:
            return True
        i = r
        # 查找第一个比头结点大的节点，分出左右子树
        for j in range(l, r):
            if postorder[j] > postorder[i]:
                i = j
                break
        # 查左右子树是否存在比头结点大或小的节点
        for j in range(l, i):
            if postorder[j] >= postorder[r]:
                return False
        for j in range(i, r):
            if postorder[j] <= postorder[r]:
                return False
        # 递归
        left = self.subTree(postorder, l, i - 1)
        right = self.subTree(postorder, i, r - 1)
        return left and right

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月2日下午3:03

思路：把问题分解为子问题，数组中最后一位是根节点，应比左子树的值大，比右子树的值小。因此遍历数字，遇到第一个比根节点大的值视为右子树的开始，遍历右子树部分，如果有一个比根节点的值小，则返回false。但是讲解里的代码写法会更好点
时间复杂段：O(N^2)
空间复杂度：O(N)

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null || postorder.length == 0) return true;
        return verifyPostorder(postorder, 0, postorder.length - 1);

    }

    public boolean verifyPostorder(int[] postorder, int l, int r){
        if(l >= r) return true;
        // 最后一位是根节点
        int len = l - r + 1;
        int rootVal = postorder[r];
        int split = r;
        int i = 0;
        while(i < r){
            if(postorder[i] > rootVal){
                split = i;
                break;  // 得到第一个大于根节点的值
            }
            i++;
        }

        while(i < r){
            if(postorder[i] < rootVal){
                return false;
            }
            i++;
        }
        return verifyPostorder(postorder, l, split - 1) && verifyPostorder(postorder, split, r - 1);
    }
}

0 赞同 0 条回复

花老爷普通 2023年7月1日下午11:35

参照leetcode评论区jyd的做法递归分治
时间：O(n^2)
空间：O(n)

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    private boolean recur(int[] postorder, int i, int j) {
        if (i >= j) {
            return true;
        }
        int p = i;
        while (postorder[p] < postorder[j]) {
            p++;
        }
        int m = p;
        while (postorder[p] > postorder[j]) {
            p++;
        }
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}

0 赞同 0 条回复

小吕普通 2023年7月1日上午9:37

c++实现
bool traversal(vector& postorder,int start,int end)
{
if(start>=end)return true;
int index = start;
while(postorder[index]<postorder[end])index++;
int midindex = index;
while(postorder[index]>postorder[end])index++;
bool left = traversal(postorder,start,midindex-1);
bool right = traversal(postorder,midindex,end-1);
return indexend&&left&&right;
}
bool verifyPostorder(vector& postorder) {
return traversal(postorder,0,postorder.size()-1);
}

0 赞同 0 条回复

行动派小彩笔普通 2023年6月30日下午8:19

//时间复杂度O(n^2),空间复杂度O(n),退化为链表,递归n次，每次都要遍历，n-1次，递归深度为n
class Solution {
public:
    bool postorderM(vector<int>& postorder,int left,int right)
    {
        if(left>=right) return true;
        int root = postorder[right];
        int index = left;
        while(postorder[index]<root)
        {
            ++index;
        }
        for(int i = index;i<right;++i)
        {
            if(postorder[i]<root)
                return false;
        }
        return postorderM(postorder,left,index-1)&&postorderM(postorder,index,right-1);
    }
    bool verifyPostorder(vector<int>& postorder) {
        return postorderM(postorder,0,postorder.size()-1);
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年6月29日下午9:42

class Solution {
public:
    bool recur(vector<int>& postorder, int i, int j){
        if(i >= j) return true;// 当 i≥j ，说明此子树节点数量 ≤1 ，无需判别正确性，因此直接返回 true
        int p = i;
        while(postorder[p] < postorder[j]) p ++;
        int m = p;
        while(postorder[p] > postorder[j]) p ++;
        return recur(postorder, i, m - 1) && recur(postorder, m, j - 1) && (p == j);
    }
    bool verifyPostorder(vector<int>& postorder) {
        return recur(postorder, 0, postorder.size() - 1);//二叉树的大小顺序排列是：左中右
    }
};
时间复杂度：O(n^2) 空间复杂度：O(n)

0 赞同 0 条回复

Vow the vow。普通 2023年6月29日下午2:45

看的参考答案的

 public boolean verifyPostorder(int[] postorder) {
        return verifyPostorder(postorder, 0, postorder.length-1);
    }

    public boolean verifyPostorder(int[] postorder, int i, int j){
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p == j && verifyPostorder(postorder,i,m-1) && verifyPostorder(postorder,m,j-1);
    }

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月29日下午1:34

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:

        def verifyPostorderHelper(i, j):
            if i >= j:
                return True

            root = postorder[j]
            p = i

            while postorder[p] < root:
                p += 1

            for k in range(p, j):
                if postorder[k] < root:
                    return False

            return verifyPostorderHelper(i, p - 1) and verifyPostorderHelper(p, j - 1)

        return verifyPostorderHelper(0, len(postorder) - 1)

python实现

0 赞同 0 条回复

怀瑾永久会员 2023年6月29日上午11:02

C++实现

#include <iostream>
#include <vector>
using namespace std;

bool verifyPostorder(vector<int>& postorder) {
    if (postorder.empty()) {
        return true;
    }

    // 调用辅助函数进行判断
    return verifyPostorderHelper(postorder, 0, postorder.size() - 1);
}

bool verifyPostorderHelper(vector<int>& postorder, int start, int end) {
    // 当前子树只有一个节点或没有节点，必定是二叉搜索树
    if (start >= end) {
        return true;
    }

    // 从左到右找到第一个大于根节点的位置
    int i = start;
    while (postorder[i] < postorder[end]) {
        ++i;
    }

    // 记录分界点
    int boundary = i;

    // 继续查找右子树，右子树的所有节点都应该大于根节点
    while (postorder[i] > postorder[end]) {
        ++i;
    }

    // 如果右子树的节点不满足大于根节点的条件，说明不是二叉搜索树
    if (i != end) {
        return false;
    }

    // 递归判断左右子树
    return verifyPostorderHelper(postorder, start, boundary - 1) && verifyPostorderHelper(postorder, boundary, end - 1);
}

int main() {
    // 输入一个整数数组
    vector<int> postorder = {5, 7, 6, 9, 11, 10, 8};

    // 判断是否是某二叉搜索树的后序遍历结果
    bool result = verifyPostorder(postorder);

    // 输出判断结果
    cout << (result ? "true" : "false") << endl;

    return 0;
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月29日上午12:16

//时间O(n^2)  空间O(n)
public boolean verifyPostorder(int[] postorder) {
        if(postorder == null || postorder.length <= 0){
            return true;
        }

        return verifyPostorder(postorder,0,postorder.length - 1);
    }

    public boolean verifyPostorder(int[] postorder,int postLeft,int postRight){
        if(postLeft >= postRight){
            return true;
        }

        int root = postorder[postRight];

        int subright = postRight;   
        for(int i = postLeft;i < postRight;i++){
            if(postorder[i] > root){    //  找到第一个大于根的树，即右子树序列的开始
                subright = i;
                break;
            }
        }

        //若没找到，此时subright指向postRight,说明没有右子树
        if(subright == postRight){
            return verifyPostorder(postorder,postLeft,subright - 1);
        }

        //判断当前树是否满足二叉搜索树，“右子树全大于根”
        for(int i = subright + 1;i < postRight;i++){
            if(postorder[i] < root){
                return false;
            }
        }

        //自己满足，还需要判断左右子数
        return verifyPostorder(postorder,postLeft,subright - 1) && verifyPostorder(postorder,subright,postRight - 1);
    }

0 赞同 0 条回复

橙子陈普通 2023年6月29日上午12:15

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if (null == postorder) {
            return true;
        }

        return f(postorder, 0, postorder.length - 1);
    }

    boolean f (int[] postorder, int i, int j) {
        if (i >= j) {
            return true;
        }

        int root = postorder[j];
        int p = i;

        // 找到第一个大于root的下标p
        while (postorder[p] < root) p++;

        // 判断p~j中是否存在小于root的值
        for (int k = p; k < j; k++){
            if (postorder[k] < root) {
                return false;
            }
        }

        // 递归左子树和右子树
        return f(postorder, i, p-1) && f(postorder, p, j-1);
    }
}

0 赞同 0 条回复

大鑫啊普通 2023年6月28日下午10:43

时间复杂度：O(n^2)
时空复杂度：O（n）
1、分析发现后续遍历的末尾元素为头结点，则以此进行划分，将数组第一个大于头结点的元素作为切分点，左边为左子树，其以及右边为右子树，再对右子树中是否存在小于当前头结点的数，有则返回false，没有则返回true，继续递归左右子树即可

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null)return true;
        return f(postorder,0,postorder.length - 1);
    }
    public boolean f(int[] postorder,int i,int j){
        if(i >= j)return true;
        int root = postorder[j];
        int p = i;
        //获取第一个大于或者等于root等元素的位置
        while(postorder[p]<root)p++;
        //判断p~j-1这个范围是否存在小于root的元素
        for(int k=p;k<j;k++){
            if(postorder[k] < root)
            return false;
        }
        return f(postorder,i,p-1) && f(postorder,p,j-1);
    }
}

0 赞同 0 条回复

Ming 普通 2023年6月28日下午9:56

通过从后往前遍历数组，模拟二叉树中右左的顺序，
平衡二叉树左小右大，所以借助辅助栈升序排放先存放父节点和后存右节点，如果当前结点小于辅助栈头结点则false否则将栈清空更新父节点

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }
}

0 赞同 0 条回复

张开怀普通 2023年6月28日下午9:49

后序遍历：左右中
后序数组中的最后一个元素为根节点，其右子树要大于根节点的，从左向右遍历数组，找到第一个比根节点大的元素，以此为切割点，分为左子树和右子树；如果切割点的右侧存在比根节点小的元素，返回false，否则按照此规律一层一层递归分割好的数组。

class Solution{
public:
       bool verifyPostorder(vector<int>& postorder){
              if(postorder.empty()){
                     return true;
              }
              function<bool(int, int)> f = [&](int i, int j){
                     if(i>=j){
                            return true;
                     }
                     int root = postorder[j];
                     int p=i;
                     while(postorder[p]<root){
                            p++;
                     }
                     for (int k=p; k<j; k++){
                            if(postorder[k]<root){
                                   return false;
                            }
                     }
                     return f(i, p-1) && f(p, j-1);
              }
              return f(0,postorder.size() - 1);
       } 
};

0 赞同 0 条回复

désire. 普通 2023年6月28日下午9:39

C++实现：
class Solution {
public:
bool verify(vector& postorder, int begin, int end)
{
if(begin >= end) return true;
int root = postorder[end];
//设置分界点
int mid = begin;
while(postorder[mid] < root)
{
mid++;
}
int temp = mid;

    while(temp < end)
    {
        if(postorder[temp] < postorder[end])
        return false;
        temp++;
    }
    //找到左子树区间和右子树区间并递归
    return verify(postorder, begin, mid - 1) && verify(postorder, mid, end - 1);

}
bool verifyPostorder(vector<int>& postorder) 
{
    return verify(postorder, 0, postorder.size() - 1);
}

};

0 赞同 0 条回复

伏月三十普通 2023年6月28日下午9:22

O(n^2)时间复杂度
O(n) 空间复杂度退化成链表

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder==null || postorder.length<=0){
            return true;
        }

        return f(postorder,0,postorder.length-1);

    }

    private boolean f(int[] postorder,int i,int j){
        if(i>=j){
            return true;
        }
        int root=postorder[j];

        int p=i;//p=0  i和j的初始值都是0
        while(postorder[p]<root){
            p++;//循环结束 p位置上对应的值是>=root
        }
        for(int k=p;k<j;k++){
            if(postorder[k]<root){  //用root 因为j会变 不要写死
                return false;
            }
        }

        return f(postorder,i,p-1) && f(postorder,p,j-1);

    }
}

0 赞同 0 条回复

yxy 普通 2023年6月28日下午8:45

复杂度O(n^2)

class Solution {
public:
    bool verify(vector<int>& postorder, int l, int r)
    {
        int sz = postorder.size();
        int i=l;
        while(i<r)
        {
            if(postorder[i]>postorder[r])
                break;
            i++;
        }
        int j=i;
        while(j<r)
        {
            if(postorder[j]<=postorder[r])
                return false;
            j++;
        }
        bool ret1=true;
        bool ret2=true;
        if(i>l)
            ret1 = verify(postorder, l, i-1);
        if(i<r)
            ret2 = verify(postorder, i, r-1);
        return ret1&&ret2;
    }
    bool verifyPostorder(vector<int>& postorder) {
        return verify(postorder, 0, postorder.size()-1);
    }
};

0 赞同 0 条回复

Dsjh 普通 2023年6月28日下午5:33

MY

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        if(postorder.size()<2){
            return true;
        }
        return myfunc(postorder,0,postorder.size()-1);
    }
    bool myfunc(vector<int>& postorder,int left,int right){
        if(left >= right){
            return true;
        }
        int root = postorder[right];
        int i=left;
        // 找到右子树第一个节点的下标
        for(;i<right;i++){
            if(postorder[i]>root)
                break;
        }
        // 右子树 > root, 否则false
        for(;i<right;i++){
            if(postorder[i]<root){
                return false;
            }
        }
        // 递归左右子树
        if(myfunc(postorder,left,i-1) && myfunc(postorder,i,right-1))
            return true;
        return false;
    }
};

0 赞同 0 条回复

【二叉树专题】剑指 Offer 33. 二叉搜索树的后序遍历序列

共以下 34 个回答

复杂度

Code

MY

# 回答此问题取消回复

【二叉树专题】剑指 Offer 33. 二叉搜索树的后序遍历序列

共以下 34 个回答

复杂度

Code

MY

# 回答此问题 取消回复

# 回答此问题取消回复