时间限制：400ms
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
- Both the left and right subtrees must also be binary search trees.
If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.
Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, first print in a line “YES” if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or “NO” if not. Then if the answer is “YES”, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input 1:
7
8 6 5 7 10 8 11
Sample Output 1:
YES
5 7 6 8 11 10 8
Sample Input 2:
7
8 10 11 8 6 7 5
Sample Output 2:
YES
11 8 10 7 5 6 8
Sample Input 3:
7
8 6 8 5 10 9 11
Sample Output 3:
NO
===================================
二叉搜索树与“镜像”的二叉搜索树，其实对称的东西只是部分特殊化了一下，所以搞定非对称的就行。
想了半天怎么用堆栈什么的实现，其实把自己绕紧了无底洞，干脆自定义结构弄嘛！
基本思路如下（对BST来说的）
工作队列q = 输入值
结果队列result = []
初始化根节点root(value)
root.left_bound = [-INF, value]
root.right_bound = [value, INF]
currNode = root
while len(q)>0 and currNode!=None:
当前队首数值为n
if n能放在当前节点左侧:
新建节点newNode
newNode.left_bound = [ currNode.left_bound[0], n]
newNode.right_bound = [ n, currNode.left_bound[1]]
newNode.parent = currNode
q.pop()
elif 能放在右侧:
新建节点newNode
newNode.left_bound = [ currNode.right_bound[0], n]
newNode.right_bound = [ n, currNode.right_bound[1]]
newNode.parent = currNode
######
currNode.cannotPlaceLeft = true
######
q.pop()
else:
result.push(currNode.value)
######
currNode.cannotPlaceLeft = true
######
currNode = currNode.parent
一切处理完之后，
while currNode != None:
result.push(currNode.value)
currNode = currNoew.parent
里面#####中间的一个布尔变量是防止重复访问左侧值设定的，比如说如下情况
8
X 10
此时左边没有东西，但是已经访问过了，如果不设置一个布尔值判断的话，假设当前有那么一个值=6的元素
当前处理位置在10，发现6放不进去，然后移到8的位置
就会觉得8左边可以塞进去
但其实已经是非法操作了
=================================================================
#include
#include
using namespace std;
const int INFI = 65535;
struct Node
{
int value;
Node* left;
Node* right;
Node* parent;
int left_bound[2];
int right_bound[2];
bool left_tried; //已经尝试过左侧
void setLeftBound(int val0, int val1)
{
left_bound[0] = val0;
left_bound[1] = val1;
}
void setRightBound(int val0, int val1)
{
right_bound[0] = val0;
right_bound[1] = val1;
}
bool canPlaceLeft(int val)
{
if(left != NULL)
return false;
if(left_tried)
return false;
if(val >= left_bound[0] && val < left_bound[1])
return true;
return false;
}
bool canPlaceRight(int val)
{
if(right != NULL)
return false;
if(val >= right_bound[0] && val < right_bound[1])
return true;
return false;
}
Node()
{
left = NULL;
right = NULL;
parent = NULL;
setLeftBound(-INFI, INFI);
setRightBound(-INFI, INFI);
left_tried = false;
}
};
queue tryBST(queue input)
{
queue result;
Node root;
root.value = input.front();
root.setLeftBound(-INFI, root.value);
root.setRightBound(root.value, INFI);
input.pop();
Node* currNode = &root;
while(!input.empty() && currNode!=NULL)
{
int currVal = input.front();
if(currNode->canPlaceLeft(currVal))
{
//可以放在左侧
Node *pNewNode = new Node;
pNewNode->setLeftBound(currNode->left_bound[0], currVal);
pNewNode->setRightBound(currVal, currNode->left_bound[1]);
pNewNode->parent = currNode;
pNewNode->value = currVal;
currNode->left = pNewNode;
currNode = pNewNode;
input.pop();
}
else if(currNode->canPlaceRight(currVal))
{
//可以放在右侧
Node *pNewNode = new Node;
pNewNode->setLeftBound(currNode->right_bound[0], currVal);
pNewNode->setRightBound(currVal, currNode->right_bound[1]);
pNewNode->parent = currNode;
pNewNode->value = currVal;
currNode->right = pNewNode;
currNode->left_tried = true;
currNode = pNewNode;
input.pop();
}
else
{
result.push(currNode->value);
currNode->left_tried = true;
currNode = currNode->parent;
}
}
while(currNode != NULL)
{
//一直递归到根部加入遍历结果
result.push(currNode->value);
currNode = currNode->parent;
}
return result;
}
queue tryBSTRev(queue input)
{
queue result;
Node root;
root.value = input.front();
root.setRightBound(-INFI, root.value);
root.setLeftBound(root.value, INFI);
input.pop();
Node* currNode = &root;
while(!input.empty() && currNode!=NULL)
{
int currVal = input.front();
if(currNode->canPlaceLeft(currVal))
{
//可以放在左侧
Node *pNewNode = new Node;
pNewNode->setRightBound(currNode->left_bound[0], currVal);
pNewNode->setLeftBound(currVal, currNode->left_bound[1]);
pNewNode->parent = currNode;
pNewNode->value = currVal;
currNode->left = pNewNode;
currNode = pNewNode;
input.pop();
}
else if(currNode->canPlaceRight(currVal))
{
//可以放在右侧
Node *pNewNode = new Node;
pNewNode->setRightBound(currNode->right_bound[0], currVal);
pNewNode->setLeftBound(currVal, currNode->right_bound[1]);
pNewNode->parent = currNode;
pNewNode->value = currVal;
currNode->right = pNewNode;
currNode->left_tried = true;
currNode = pNewNode;
input.pop();
}
else
{
result.push(currNode->value);
currNode->left_tried = true;
currNode = currNode->parent;
}
}
while(currNode != NULL)
{
//一直递归到根部加入遍历结果
result.push(currNode->value);
currNode = currNode->parent;
}
return result;
}
int main()
{
queue input;
int N;
scanf("%d", &N);
for(int i=0; i result1 = tryBST(input);
if(result1.size() == input.size())
{
printf("YESn");
while(!result1.empty())
{
printf("%d", result1.front());
if(result1.size() != 1)
printf(" ");
result1.pop();
}
return 0;
}
result1 = tryBSTRev(input);
if(result1.size() == input.size())
{
printf("YESn");
while(!result1.empty())
{
printf("%d", result1.front());
if(result1.size() != 1)
printf(" ");
result1.pop();
}
return 0;
}
printf("NO");
//
return 0;
}
测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 0 710 6/6
1 答案正确 0 790 6/6
2 答案正确 0 710 2/2
3 答案正确 0 720 3/3
4 答案正确 0 790 3/3
5 答案正确 0 700 2/2
6 答案正确 0 790 2/2
7 答案正确 0 790 1/1