1043 Is It a Binary Search Tree（二叉查找树BST）

野性酷女 2024-04-07 12:22 77阅读 0赞

## 1043 Is It a Binary Search Tree ##

### 0、题目 ###

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: ####

### 1、大致题意 ###

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

### 2、基本思路 ###

#### 2.1 二叉排序树 ####

二叉排序树有以下的性质：

*  左边结点的值比其父节点的值小
 *  右边结点的值大于或等于其父节点的值
 *  左子树和右子树都必须是二叉树

##### 2.1.1 二叉排序树的镜像 #####

如果交换左右结点的值，那么形成的二叉排序树就是原二叉排序树的镜像。现给出一串整数序列，你需要判断该序列是否是一棵二叉排序树或二叉排序树的镜像的先序序列，并输出其后序序列。

#### 2.2 解题思路 ####

首先边输入结点的值边插入形成一棵二叉排序树，见函数`build()`；

接着对构建好的二叉排序树进行先序`preOrder()`、镜像先序`mirrorPreOrder()`和后序`postOrder()`、镜像后序`mirrorPostOrder()`遍历；

最后判断题目给出的序列和先序遍历结果、镜像先序遍历结果是否一致，输出结果即可。

*  先序遍历：根节点、左子树、右子树（中左右）
 *  镜像先序遍历：根节点、右子树、左子树（中右左）
 *  后序遍历：左子树、右子树、根节点（左右中）
 *  镜像后序遍历：右子树、左子树、根节点（右左中）

#### 2.3 补充-C++中如何判断两个vector是否相等？ ####

直接使用`==`呀

如果vector里面的元素类型是简单类型（内置类型），可以直接使用`==`或者`!=`进行比较  
因为在`STL`里面，`==`和`!=`是可以直接使用的：

template< class T, class Alloc >
    bool operator==( const vector<T,Alloc>& lhs,
                     const vector<T,Alloc>& rhs );
    
    template< class T, class Alloc >
    bool operator!=( const vector<T,Alloc>& lhs,
                     const vector<T,Alloc>& rhs );

甚至可以使用`<=`、`<`、`>=`、`>`比较两个vector大小：按照字典序排列

template< class T, class Alloc >
    bool operator<( const vector<T,Alloc>& lhs,
                    const vector<T,Alloc>& rhs );
    
    template< class T, class Alloc >
    bool operator<=( const vector<T,Alloc>& lhs,
                     const vector<T,Alloc>& rhs );
    
    template< class T, class Alloc >
    bool operator>( const vector<T,Alloc>& lhs,
                    const vector<T,Alloc>& rhs );
    
    template< class T, class Alloc >
    bool operator>=( const vector<T,Alloc>& lhs,
                     const vector<T,Alloc>& rhs );

### 3、AC代码 ###

#include<iostream>
    #include<vector>
    using namespace std;
    struct Node{
        
    	int data;
    	Node *left,*right;
    };
    int N;
    vector<int> origin,pre,preMirror,post,postMirror;
    Node *tree = NULL;
    int sum = 0;
    //构建二叉排序树 
    void build(Node* &node,int data){
        
    	sum ++;
    	if(node == NULL){
        
    		node = new Node;
    		node->data = data;
    		node->left = node->right = NULL;
    		return;
    	}
    	if(data < node->data)
    		build(node->left,data);
    	else
    		build(node->right,data);
    }
    //先序遍历 
    void preOrder(Node* tree){
        
    	if(tree == NULL)
    		return;
    	pre.push_back(tree->data);
    	preOrder(tree->left);
    	preOrder(tree->right);
    }
    //先序遍历镜像
    void mirrorPreOrder(Node *tree){
        
    	if(tree == NULL)
    		return;
    	preMirror.push_back(tree->data);
    	mirrorPreOrder(tree->right);
    	mirrorPreOrder(tree->left);
    }
    //后序遍历
    void postOrder(Node *tree){
        
    	if(tree == NULL)
    		return;
    	postOrder(tree->left);
    	postOrder(tree->right);
    	post.push_back(tree->data);
    } 
    //后序遍历镜像 
    void mirrorPostOrder(Node *tree){
        
    	if(tree == NULL)
    		return;
    	mirrorPostOrder(tree->right);
    	mirrorPostOrder(tree->left);
    	postMirror.push_back(tree->data);
    } 
     
    int main(){
        
    	scanf("%d",&N);
    	for(int i = 0 ; i < N ; i ++){
        
    		int temp;
    		scanf("%d",&temp);
    		origin.push_back(temp);
    		build(tree,origin[i]);//构建二叉排序树 
    	}
    	preOrder(tree);
    	mirrorPreOrder(tree);
    	postOrder(tree);
    	mirrorPostOrder(tree);
    	if(pre == origin){
        //初始序列等于先序序列 
    		printf("YES\n");
    		for(int i = 0 ; i < post.size() ; i ++){
        
    			if(i > 0)
    				printf(" ");
    			printf("%d",post[i]);
    		}
    	}else if(preMirror == origin){
        //初始序列等于先序镜像序列 
    		printf("YES\n");
    		for(int i = 0 ; i < postMirror.size() ; i ++){
        
    			if(i > 0)
    				printf(" ");
    			printf("%d",postMirror[i]);
    		}
    	}else{
        
    		printf("NO");
    	}
    	return 0; 
    }