剑指offer23 判断是否为二叉搜索树的后序遍历

本文主要是介绍剑指offer23 判断是否为二叉搜索树的后序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

总结：后序遍历特征：最后一个为根节点，从第一个数字开始直到第一个比根节点大的数字都是左子树，后面都是右子树都应该比根节点大一旦有小的就判断不是，程序里用到了不设置初始值的循环。一般搜索树都是用递归。

class Solution {
public:bool VerifySquenceOfBST(vector<int> sequence) {int len =sequence.size();if(len==0) return false;vector <int>left,right;int i=0;for(;i<len-1;i++){if(sequence[i]<sequence[len-1])left.push_back(sequence[i]);else break;}for(;i<len-1;i++){if(sequence[i]>sequence[len-1])right.push_back(sequence[i]);else return false;}bool left1=true,right1=true;if(!left.empty())left1=VerifySquenceOfBST(left);//递归判断左子树if(!right.empty())right1=VerifySquenceOfBST(right);//递归判断右子树return left1&&right1;}
};

 

这篇关于剑指offer23 判断是否为二叉搜索树的后序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---