AlgoPressAppearance
33-二叉搜索树的后序遍历序列
题目描述
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
提示：
数组长度 <= 1000
思路分析
后续遍历 : 左右根 二叉搜索树 ：左子树 都 小于右子树 所以 ：最后一个数，一定是中间的数字，找到中间边界，左边的数字都小于它，右边的数字都必须大于他
实现代码
csharp
public class Solution {
private int[] CopyArray(int[] arr, int start, int end){
//Console.WriteLine("start:{0},end:{1}",start,end);
int[] resultArr = new int[end - start +1];
int index = 0;
for(int i=start; i<=end; i++){
resultArr[index]= arr[i];
index++;
}
return resultArr;
}
public bool VerifyPostorder(int[] postorder) {
//Console.WriteLine("Array Length {0} ", postorder.Length);
if(postorder.Length < 2){
return true;
}
int rootNumber = postorder[postorder.Length - 1];
//寻找中间数
int mid = 0;
for(int i=0; i<postorder.Length-1; i++){
if(postorder[i] < rootNumber){
mid++;
}
else{
break;
}
}
//Console.WriteLine("rootNumber:{0},mid:{1}",rootNumber,mid);
//验证左右是否相等
for(int i=mid; i < postorder.Length - 1; i++){
if(postorder[i] <= rootNumber){
return false;
}
}
//验证子串
bool result = true;
if(mid < postorder.Length -2){
result = result && VerifyPostorder(CopyArray(postorder,mid,postorder.Length-2));
}
if(mid > 0){
result = result && VerifyPostorder(CopyArray(postorder, 0,mid-1));
}
return result;
}
}
实现代码:不复制数组
csharp
public class Solution {
private bool verifyPostorder(int[] postorder, int start, int end){
//结束条件
if(end - start <=1){
return true;
}
int root = postorder[end];
//find mid
int mid = int.MaxValue;
for(int i=start; i<end; i++ ){
if(postorder[i] > root){
mid = i;
break;
}
}
//判断右边
for(int i=mid; i<end; i++){
if(postorder[i] < root){
return false;
}
}
//递归判断
if(mid == int.MaxValue){
return verifyPostorder(postorder,start,end-1);
}
else{
bool result = verifyPostorder(postorder, start, mid-1);
result = result && verifyPostorder(postorder, mid, end-1);
return result;
}
}
public bool VerifyPostorder(int[] postorder) {
return verifyPostorder(postorder,0,postorder.Length-1);
}
}