剑指 Offer 33. 二叉搜索树的后序遍历序列

2023-07-08 09:57| 来源: 网络整理| 查看: 265

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

观察数组我们可以得到一些初始数据。

数组的最后一位元素为根。根的左子树小于根数据，右子树大于根数据。如果数组为真的后序排列，那么我们的数组就是前半部分值绝对小于根数据，后半部分值绝对大于根数据。

左右分割数组。寻找分割左右的分割点-->从左到右第一个大于根的结点。

继续向后，这个时候index比根数据大就向后走，直到大于或小于

完整图

代码细节讲解。

//利用子函数递归解决问题 bool ans(const vector& postorder, int state, int end) { //如果当前数组访问只有一个就返回真 if (state >= end) { return true; } //初始化寻找指针到数组开头 int index = state; while (postorder[index] < postorder[end]) { //寻找根的右子树第一个访问的结点 index++; } //找到右子树的第一个访问结点，标记位置。 int mid = index; while (postorder[index] > postorder[end]) { index++; } // //如果当前根结点的: // 左子树所有结点都小于根数据 // 右子树所有结点都大于根数据 if (index != end) {//如果index不等于end，意味着不为搜索树 return false; } bool left = ans(postorder, state, mid - 1); //去左子树判断进行递归，如果返回左子树判断结果， //mid是右子树的第一个访问结点，所以我们需要mid-1传到下一级形参end中。 if (!left)//如果左子树不是搜索树直接返回false，不再去右子树寻找 { return false; } bool right = ans(postorder, mid + 1, end);//与左子树同理 if (!right) { return false; } return true;//index==end为真，左子树为真，右子树为真，返回真 } bool verifyPostorder(const vector& postorder) { return ans(postorder, 0, postorder.size() - 1); }

【本文地址】

公司简介

联系我们