PAT A 甲级 1043 Is It a Binary Search Tree (25分)
63 浏览量
2021-01-20
13:36:01
上传
评论
收藏 53KB PDF 举报
PAT A 甲级甲级 1043 Is It a Binary Search Tree (25分分)
1043 Is It a Binary Search Tree (25分分)
吐槽吐槽
……感觉二叉树是甲级里最难的一类题了……比图论还难。要变通和自己思考逻辑的部分实在太多了。
思路思路
首先这道题是“非常规”的，这题不是“这个二叉树是不是搜索树”，而是“这遍历有没有可能是某个搜索树的先序遍历”。正常情况
下需要两种遍历才能确立一棵二叉树，但这道题却只给了一种遍历。
不过，“二叉搜索树”本身是有条件的，正是这个条件使得这种确定可以在只有先序遍历的情况下实现。
我首先想到的是二叉搜索树的中序遍历就是数字的从到大（或者镜像的话是从大到小，后面只分析非镜像搜索树），可以靠这
一点直接获得一个中序遍历从而用两个遍历确定一颗二叉树。
但是这里就遇到了一个问题——如果不是二叉搜索树，该怎么报错跳出？这个过程中有没有可能产生不可靠的代码？
其次，这颗树的数据也比较特殊——它各个数字是有概率不止出现一次的。这种情况下，一般的“靠先序遍历找到根结点后从
中序中找到左右子树”，对于多次出现的数字，判断哪个才是要找的这个根节点会很麻烦。
但是这时我才突然意识到，根本不需要中序队列啊。
在前/后序+中序确定树的逻辑中，前/后序用来确定一个树内的根节点，而中序队列用来找到它的左右子树范围，但对于二叉
搜索树，这完全没有必要——比该节点小的就在左子树里，大的就在右子树里啊。并且，应该是成块的，也就是应该某个位置
前都比根小，后都比根大。
所以要做的只是——对于一颗子树，第一个数是根节点，找到后面的区块中第一个大于等于它的数，如果这个数之后还有比这
个节点小的，那就不是二叉搜索树，如果全列都没有这个问题，那就是二叉搜索树。
而且，用来干这件事的这个递归还可以顺带用来输出后序。
代码代码
#include
#include
#include
using namespace std;
vector preorder;
bool ifm = false;
queue bip;
queue mbip;
bool ifbi(int leftb, int rightb)
{
int i;
int block;
bool leftt = true;
bool rightt = true;
if (leftb >= rightb)
return true;
for (i = leftb + 1; i = preorder[leftb]))
break;
else if (ifm && (preorder[i] < preorder[leftb]))
break;
}
block = i;
for (; i < rightb; i++)
{
if (!ifm && (preorder[i] = preorder[leftb]))
return false;
}
if (leftb + 1 < block)
leftt = ifbi(leftb + 1, block);
if (block > n;
int i;
int temp;
bool bi = false;
bool mbi = false;
for (i = 0; i > temp;
preorder.push_back(temp);
资源评论
