本文主要是介绍剑指 offer 判断一棵树是不是后序遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
class Solution {
public:bool VerifySquenceOfBST(vector<int> sequence) {return bst(sequence, 0, sequence.size() - 1);}
private:bool bst(vector<int> seq, int begin, int end){// 边界条件if(seq.empty() || begin > end)return false;// 划分左右子树,并判断左右子树和根节点的关系int i = begin;for(; i < end; ++i)if(seq[i] > seq[end])break;int j = i;for(; j < end; ++j)if(seq[j] < seq[end])return false;// 判断左子树是不是二叉搜索树bool left = true;if(i > begin)left = bst(seq, begin, i - 1);// 判断右子树是不是二叉搜索树bool right = true;if(i < end - 1)right = bst(seq, i , end - 1);return left && right;}
};
这篇关于剑指 offer 判断一棵树是不是后序遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!