平面设计跟网站建设,公司邮箱登陆,承包活应该上什么平台,免费网页制作文章目录一、题目描述二、示例三、主要思路一、题目描述 输入一个整数数组#xff0c;判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。 提示#xff1a; 1.二叉搜索树是指父亲节点大于左子树中…
文章目录一、题目描述二、示例三、主要思路一、题目描述 输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。 提示 1.二叉搜索树是指父亲节点大于左子树中的全部节点但是小于右子树中的全部节点的树。 2.该题我们约定空树不是二叉搜索树 3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历 二、示例 示例一 输入[1,3,2] 返回值true 示例二 输入[3,1,2] 返回值false 示例三 输入[5,7,6,9,11,10,8] 返回值true 三、主要思路
这道题可以用分治的思想来解决首先我们要找到这棵二叉搜索树的根节点由于给出的序列是后序遍历序列所以序列的最后一个元素一定就是根节点。
二叉搜索树的特性是左子树所有节点的值一定比根节点的值小右子树所有节点的值一定比根节点的值大题目说明了序列中不存在两个重复的数字。
所以我们要做的是两步确定序列中的左子树区间和右子树区间、检测区间内的值是否符合规定。
首先是确定序列中左子树的区间我们从左到右遍历序列如果当前的值比根节点的值小则继续遍历直到出现第一个比根节点大的值时我们就能够确定下左子树的区间范围了。
然后从第一个比根节点大的值开始按理说往后一定是右子树区间也就是说往后的值一定都比根节点的值大否则就说明这不是符合规定的序列。因此我们需要检测右子树区间是否符合规定当发现存在一个比根节点小的值时就可以直接返回false了。
如果右子树区间也没有问题那就继续将左右子树区间当成一个新的序列划分将问题规模变小当划分成不可分割的子问题时如果所有区间都符合规定则证明该序列是正确的二叉搜索树后序遍历序列。
class Solution {
public:bool _VerifySquenceOfBST(vectorint a, int start, int end){if(start end){return true;}// 后序遍历数组的最后一个元素一定是根节点int root a[end];// 确定根节点的左子树区间范围int i start;while(i end a[i] root){i;}// 检测i往后的值是否都是大于rootfor(int j i; j end; j){if(a[j] root){return false;}}// 走到这里说明区间检测正确继续分治检测return _VerifySquenceOfBST(a, start, i - 1) _VerifySquenceOfBST(a, i, end - 1);}bool VerifySquenceOfBST(vectorint sequence) {if(sequence.empty()){return false;}return _VerifySquenceOfBST(sequence, 0, sequence.size() - 1);}
};
