public class 二叉搜索树的后序遍历序列 {
public static void main(String[] args) {
int[] postorder = {1,3,2,6,5};
System.out.println(verifyPostorder(postorder));
}
public static boolean verifyPostorder(int[] postorder) {
int n = postorder.length;
int i=0,j=n-1;
if(i>=j) return true;
return myVerifyPostorder(postorder,i,j);
}
private static boolean myVerifyPostorder(int[] postorder, int i, int j) {
if(i>=j) return true;
int num=postorder[i];
int k=i;
while(postorder[k]<postorder[j]) k++;
int m = k;
while(postorder[k]>postorder[j]) k++;
return k==j&&myVerifyPostorder(postorder,i,m-1)&&myVerifyPostorder(postorder,m,j-1);
}
}
function verifyPostorder(postorder: number[]): boolean {
const dfs = (l: number, r: number) => {
if (l >= r) return true;
let x = l;
while (postorder[x] < postorder[r]) x++;
let y = x;
while (postorder[y] > postorder[r]) y++;
return y === r && dfs(l, x - 1) && dfs(x, r - 1);
}
return dfs(0, postorder.length - 1);
};
func verifyPostorder(postorder []int) bool { //分治法
if len(postorder) == 0 {
return true
}
if len(postorder) == 1 {
return true
}
var ans bool = true
var mid int = 0
var n int = len(postorder)
var flag int = postorder[n-1]
var isvis bool = false
for i:=0 ; i < n-1 ; i++ {
if i == 0 && postorder[i] > flag {
mid = i
isvis = true
}else if i == n-2 && postorder[i] < flag {
if isvis == true {
return false
}
mid = n-1
isvis = true
}else if postorder[i] < flag && flag < postorder[i+1] && isvis == false{
mid = i+1
isvis = true
}else if postorder[i] < flag && flag < postorder[i+1] && isvis == true {
return false //如果重复出现分裂点则肯定不对
}
}
ans = ans && verifyPostorder(postorder[0:mid]) && verifyPostorder(postorder[mid:n-1])
return ans
}
九
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);
}
}
shuaidi
共以下 30 个回答
//遍历 ，对每一个根节点判断是否满足二叉搜索树后序序列& postorder) {
//左右根，根据根的值确定左右子树结点，然后计算包括左子节点前所有的结点都小于根，右子节点都大于根
//基于数组操作的
class Solution {
public:
bool verifyPostorder(vector
bool flg = true;
int len = postorder.size();
for(int i=0; i < len; i++){
flg = check(postorder, i);
if(!flg) return false;
}
return true;
}
};
class Solution {& postorder, int start, int end) {
public:
bool traversal(vector
/* 递归终止条件 /
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);
// index end判断是否为二叉搜索树
return index end && left && right;
}
};
ts
时间复杂度：O（n^2）
空间复杂度：O（n）
时间复杂度：O（n2)
空间复杂度：O（n)
c++代码，递归分治的思想& postorder) & postorder,int start,int end)
class Solution {
public:
bool verifyPostorder(vector
{
return istrue(postorder,0,postorder.size()-1);
}
bool istrue(vector
{
if(start>=end) return true;
int index=start;
while(postorder[index]<postorder[end])index++;//找到第一个大于根节点的值
int te=index;
while(postorder[index]>postorder[end]) index++;//判断右子树是否大于根节点
return indexend&&istrue(postorder,start,te-1)&&istrue(postorder,te,end-1);
}
};
递归栈是O(n) 时间复杂度也为O(n)
递归实现
代码
TS写的
”’java
class Solution {
public boolean verifyPostorder(int[] postorder) {
//二叉搜索树中根结点的值大于左子树中任何一个结点的值，小于右子树中任何一个结点的值，子树也是
return verify(postorder,0,postorder.length-1);
}
//递归
private boolean verify(int[] postorder,int left,int right){
if(left >= right){
return true;
}
//最后一个结点是根结点
int root = postorder[right];
//先寻找右子树
int rightNode = right;
for(int i = right-1;i >= left;i–){
if(postorder[i] < root){
rightNode = i;
break;
}
}
rightNode = rightNode right ? left:rightNode+1;
for(int i = left;i < rightNode;i++){
if(postorder[i] > root){
return false;
}
}
boolean flagRight = verify(postorder,rightNode,right-1);
boolean flagLeft = verify(postorder,left,rightNode-1);
return flagRight && flagLeft;
}
时间复杂度O(n)
空间复杂度O(1)
”’
时间复杂度： O(nlog(n))
class Solution {
public boolean verifyPostorder(int[] postorder) {
//二叉搜索树 左子树比根节点小 右子树一定比根节点大
//后序遍历 左右根 小 大 小
//可以倒序 变成 根右左 先找第一个小于它 归为右子树 后面变成左子树
if(postordernull||postorder.length0)
{
return true;
}
return verifyPostorder1(postorder,0,postorder.length-1);
}
思路
首先需要了解后序遍历，数组的最后一个元素就是根节点，前面分成两个部分，先是左子树然后是右子树。
这道题目用的是BST，BST的特点就是左子树的数值都比root的数值校，右子树都比root大。
所以一个正确的BST的后序遍历数组应该是：从头开始遍历找到的第一个比root大的数，前面的都是左子树，之后到最后一个元素之前都是右子树。
据此，可以写出以下代码。由于子树中的所有节点的值都小于root，但是子树中还有子树，所以需要用递归来判断所有的节点。
代码
九
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);
}
}
“`c++& nums,int l,int r)nums[r]) i++; & postorder) {
//递归
class Solution {
public:
bool dfs(vector
{
if(l>=r) return true;
int i=l;
while(nums[i]
return i==r&&dfs(nums,l,j-1)&&dfs(nums,j,r-1);
}
bool verifyPostorder(vector
return dfs(postorder,0,postorder.size()-1);
}
};
Day9：下面是代码
时间复杂度:O(nlogn)
空间复杂度：O(n)
通过单调栈，从后往前左子树一直大于根节点
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
stack, root = [], float(“+inf”)
for i in range(len(postorder) – 1, -1, -1):
if postorder[i] > root: return False
while(stack and postorder[i] < stack[-1]):
root = stack.pop()
stack.append(postorder[i])
return True
O(N)
O(N)
代码如下
时间复杂度：O(n^2)
空间复杂度：O(n)
时间复杂度：O(n)
空间复杂度：o(n)