剑指Offer33.二叉搜索树的后序遍历序列 C++

news/2024/11/17 5:47:39/

1、题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/
2 6
/
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true

2、VS2019上运行

使用递归的方法

#include <iostream>
#include <vector>using namespace std;class Solution {
public:bool verifyPostorder(vector<int>& postorder) {//划分点 pivot 等于右边界 right，并且左子树和右子树都是有效的二叉搜索树return helper(postorder, 0, postorder.size() - 1);}private:bool helper(vector<int>& postorder, int left, int right) {// 基本情况：空子树或单个节点，也是一个二叉搜索树if (left >= right) {return true;}int pivot = left;//表示当前子树的左边界//找到当前子树中第一个大于根节点值的元素的位置，将其作为划分点while (postorder[pivot] < postorder[right]) {++pivot;//表示划分节点的位置}int mid = pivot; // 划分点while (postorder[pivot] > postorder[right]) {++pivot;}// 此时pivot应该指向右侧大于根节点的最右元素// 如果pivot不等于right，意味着划分点之后的一些元素小于根节点---不是二叉搜索树// 如果pivot等于right，意味着划分点之后的所有元素都大于根节点。// 递归检查左右子树，左子树和右子树必须都是有效的二叉搜索树return pivot == right && helper(postorder, left, mid - 1) && helper(postorder, mid, right - 1);}
};int main() {vector<int> postorder = { 1, 3, 2, 6, 5 };Solution solution;bool isValidBST = solution.verifyPostorder(postorder);cout << "给定的后序遍历是有效的二叉搜索树吗？" << (isValidBST ? "是" : "否") << endl;return 0;
}