二叉搜索树满足哪些条件

本文已参与「新人创作礼」活动，一起开启掘金创作之路。

二叉搜索树的后续遍历

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

参考以下这颗二叉搜索树：

 5 / \ 2 6 / \ 1 3 

示例1：

输入: [1,6,3,2,5] 输出: false 示例2： 输入: [1,3,2,6,5] 输出: true 提示： 数组长度 <= 1000

方法一：暴力求树的存在性

刚看到这题直接的想法就是：由于我们知道了后续遍历，即左-右-根的序列，而且又是二叉搜索树，所以中序遍历（左-根-右）的顺序就是后续遍历的的从小到大排序。为了方便，将后续遍历翻转，即得到了根-右-左的排序，记 lmr（left-mid-right)=中序遍历的序列，mrl=后续遍历的翻转。 这样有了lmr和mrl就可以唯一的确定一棵树了，所以只需要根据这两个序列能够构造出一棵二叉树，就可以知道后续序列是否是某个搜索二叉树的后续遍历了。 具体构造树的方法为：取mrl第一个值即为根，然后在lmr中找到根的值，左侧即为左子树，右侧为右子树，再从mrl中的第一个元素开始取lmr左子树的个数个元素，重复完成上述操作（即递归求解左子树的存在性），右子树也是同理。如果左右子树都存在那么，这棵树也就存在。要注意的是递归时lmr和mrl的元素必须一一对应。 代码如下：

vector<int> mrl; vector<int> lmr; bool check(int mrlbegin, int mrlend, int lmrbegin, int lmrend) { if(mrlend == mrlbegin && lmrend == lmrbegin) return true; else if(mrlend - mrlbegin != lmrend - lmrbegin) return false; for(int i = mrlbegin; i <= mrlend; i ++) { bool flag = false; for(int j = lmrbegin; j <= lmrend; j ++) { if(mrl[i] == lmr[j]) { flag = true; break; } } if(!flag) return false; } int root = mrl[mrlbegin]; int ptr = lmrbegin; for(; ptr <= lmrend; ptr ++) { if(lmr[ptr] == root) { break; } } if(ptr > lmrend) return false; bool ans1 = true; bool ans2 = true; if(mrlbegin + 1 >= 0 && mrlbegin + 1 <= mrlbegin + lmrend - ptr && mrlbegin + lmrend - ptr < mrl.size() && ptr + 1 <= lmrend) ans1 = check(mrlbegin + 1, mrlbegin + lmrend - ptr, ptr + 1, lmrend); if(mrlbegin + ptr - lmrbegin + 1 >= 0 && mrlbegin + lmrend - ptr + 1 <= mrlend && lmrbegin <= ptr - 1 && ptr - 1 < lmr.size()) ans2 = check(mrlbegin + lmrend - ptr + 1, mrlend, lmrbegin, ptr - 1); return ans1 && ans2; } bool verifyPostorder(vector<int>& postorder) { if(postorder.size() == 0) return true; mrl = vector<int>{}; for(int i = postorder.size() - 1; i >= 0; i --) mrl.push_back(postorder[i]); lmr = postorder; sort(lmr.begin(), lmr.end()); return check(0, mrl.size() - 1, 0, lmr.size() - 1); } 

但是这样实在是太复杂了，我在做这道题时肯定不会这样做的（这个是我在提交后又写的，已经通过了测试，可以放心食用，但是时间复杂度太高了，还是建议看下面的解法）

方法二：单调栈

这个解法是看到题解中有用栈的方法去解的（但是没看具体操作方法），经过很长一段时间的思考，终于想到了这种用栈的解法，最后与题解对比，思路基本一致（方法名叫做单调栈，可能是与栈中的单调性有关），下面是具体做法。只要所有元素都遍历完，那么就说明此序列是一个二叉搜索树的后续遍历，返回true。 代码如下：

bool verifyPostorder(vector<int>& postorder) { stack<int> s; int rootval = ; int cur = postorder.size() - 1; if(postorder.size() == 0) return true; else s.push(postorder[cur]); cur --; while(cur >= 0) { if(postorder[cur] > rootval) return false; if(!s.empty()) { if(postorder[cur] > s.top()) { s.push(postorder[cur]); cur --; } else { while(!s.empty() && postorder[cur] < s.top()) { rootval = s.top(); s.pop(); } } } else { s.push(postorder[cur]); cur --; } } return true; }