【C/C++练习题】二叉搜索树的后序遍历序列
【摘要】
《剑指Offer》面试题33：二叉搜索树的后序遍历序列
1 题目
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
2 思路
二叉搜索树的所有左子树节点都小于等于根节点，所有右子树节点都大于等于根节...
《剑指Offer》面试题33：二叉搜索树的后序遍历序列
1 题目
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
2 思路
二叉搜索树的所有左子树节点都小于等于根节点，所有右子树节点都大于等于根节点。而后序遍历的优先遍历顺序是，左子节点->右子节点->根节点。
那么，将序列分成左子树节点、右子树节点、根节点三个部分，取序列中最后一个元素为当前二叉树的根节点，在判断左右区间中的节点是否满足搜索二叉树的定义，如果满足就对剩下的左右区间进行递归，否则返回false。当递归至树中只有一个节点的时候，返回true。
3 代码
-
/*
-
*********************************************************************************************************
-
*
-
* 模块名称 : 主程序
-
* 文件名称 : demo.cpp
-
* 版 本 : V1.0
-
* 说 明 : 《剑指Offer》笔试题，确定二叉搜索树的后序遍历序列
-
*
-
* 修改记录 :
-
* 版本号 日期 作者 说明
-
* V1.0 2019-08-13 hinzer 正式发布
-
*
-
* 码云链接：
-
*
-
*********************************************************************************************************
-
*/
-
-
#include "iostream"
-
#include "cstdlib"
-
-
using namespace std;
-
-
-
typedef struct Node
-
{
-
int m_nValue;
-
Node* m_pLeft;
-
Node* m_pRight;
-
}BinaryTreeNode;
-
-
-
/******************************************************************************
-
* 函数介绍：确定为二叉搜索树的后序遍历序列
-
* 输入参数：array待判断的数组序列, length序列长度
-
* 输出参数：无
-
* 返回值：true 成功 , false 传入参数无效
-
* 备注：无
-
******************************************************************************/
-
bool Is_squence_of_BST(const int* array, int length)
-
{
-
//判断无效输入参数
-
if (NULL == array || length <= 0)
-
return false;
-
-
//1.递归算法-回归条件
-
if (length == 1)
-
{
-
return true;
-
}
-
-
//2.根据二叉搜索树的规则，判断左子树区间和右子树区间
-
int i = 0; //
-
while (!(array[i] <= array[length-1] && array[length-1] <= array[i+1]))
-
{
-
++i;
-
//防止数组越界
-
if (i == length-1)
-
return false;
-
}
-
-
//3.判断左子树节点 <= 根节点 <= 右子树节点
-
int j = 0;
-
for (j = 0;j <= i;++j)
-
{//对左子树节点进行判断
-
if (array[j] > array[length-1])
-
return false;
-
}
-
for (j = i+1;j <= length-2;++j)
-
{//对右子树节点进行判断
-
if (array[j] < array[length-1])
-
return false;
-
}
-
-
//4.递归算法-递推公式
-
return (Is_squence_of_BST(&array[0], i+1) && Is_squence_of_BST(&array[i+1], length-i-2));
-
}
-
-
-
-
-
/******************************************************************************
-
* 函数介绍：功能测试函数
-
* 输入参数：无
-
* 输出参数：无
-
* 返回值：无
-
* 备注：无
-
******************************************************************************/
-
void test01()
-
{
-
int array1[] = {5, 7, 6, 9, 11, 10, 8};
-
int array2[] = {7, 4, 6, 5};
-
-
if (Is_squence_of_BST(array1, sizeof(array1)/sizeof(int)))
-
{
-
cout << "array1 is correct" << endl;
-
}
-
if (Is_squence_of_BST(array2, sizeof(array2)/sizeof(int)))
-
{
-
cout << "array2 is correct" << endl;
-
}
-
-
}
-
-
-
int main(int argc, char const *argv[])
-
{
-
test01();
-
return 0;
-
}
4 运行
5 算法改进
-
bool Is_squence_of_BST(const int* array, int length)
-
{
-
//判断无效输入参数
-
if (NULL == array || length <= 0)
-
return false;
-
-
//1.递归算法-回归条件
-
if (length == 1)
-
{
-
return true;
-
}
-
-
//2.根据二叉搜索树的规则，判断左子树区间和右子树区间
-
int i = 0;
-
for (i = 0;i < length-1;++i)
-
{//搜索二叉树中，左子树节点小于根节点
-
if (array[i] > array[length-1])
-
break;
-
}
-
-
int j = 0;
-
for (j = i;j < length-1;++j)
-
{//搜索二叉树中，右节点的值大于根节点
-
if (array[j] < array[length-1])
-
return false;
-
}
-
-
//3.递归算法-递推公式
-
return (Is_squence_of_BST(&array[0], i) && Is_squence_of_BST(&array[i], length-i-1));
-
}
文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/feit2417/article/details/99469040
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）