判断一个给定数组是否为二叉搜索树后序遍历

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

判断一个给定数组是否为二叉搜索树后序遍历

2023-02-16 17:58:20 来源：博客园

问题：判定一给定数组是否为二叉搜索树的后序遍历结果面试题33. 二叉搜索树的后序遍历序列（递归分治 / 单调栈，清晰图解） - 二叉搜索树的后序遍历序列 - 力扣（LeetCode）

思路一：递归数组最后一个数必为根节点 ,下标记为 j ，以此节点为左右子树的分界线，

从前往后遍历数组，找到第一个比根节点大的数，下标记为m；那么m之前的都是小于根节点的；[ i , m-1 ]

(资料图片)

判定该下标m之后的数是否都大于根节点；并且判断最后下标是否与根节点下标相等，则该根节点满足条件，[ m , j -1 ] ，

继续缩小范围递归判定左右子树是否满足，逻辑与；[ i , m-1 ] <[ m , j -1 ] ,

时间复杂度：O(N²) ;空间复杂度：O(N)

class Solution {public:    bool verifyPostorder(vector& postorder) {        return recur(postorder,0,postorder.size()-1);    }private:    bool recur(vector& postorder,int i,int j){        if(i>=j) return true;        int p = i;        while(postorder[p] postorder[j]) ++p;        return p==j && recur(postorder,i,m-1) && recur(postorder,m,j-1);    }};

思路二：观察倒序 + 单调栈

倒序：将后续遍历镜像，根--右--左；

若是递增，则说明当前节点为前一个节点的右子节点；

若是递减，则是前面节点中，大于当前节点且是最小的那个节点(父节点) 的左子节点，且当前节点之后的节点都小于那个父节点，若满足则为二叉搜索树；

借此可以辅助栈，将递增序列的节点依次压入栈中，判断当前栈顶节点与下一个当前节点大小，递增就继续压栈，

递减，栈不为空且当前节点小于栈顶元素，循环出栈顶，设置一个父节点存储栈顶，遍历完则说明满足

class Solution {public:    bool verifyPostorder(vector& postorder) {        stacktmp;        int max_num = INT_MAX;         for(int i = postorder.size()-1;i>=0;--i){            if(postorder[i] > max_num) return false;            while(tmp.size() && postorder[i] < tmp.top()){                max_num = tmp.top();                tmp.pop();            }            tmp.push(postorder[i]);        }        return true;    }};

关键词：满足条件时间复杂度