PAT--1043 Is It a Binary Search Tree(二叉排序树的建立与判定)-白红宇

PAT--1043 Is It a Binary Search Tree(二叉排序树的建立与判定)

阅读量：197 次

发布时间：2019-02-28

本文共 1917 字，大约阅读时间需要 6 分钟。

如何判断一个输入序列是否是一颗二叉排序树的前序序列或是其镜像树的前序序列？以下是详细的解决方法。

方法一：构建两棵树并进行前序遍历

构建二叉排序树和镜像树：

二叉排序树：按照递增顺序插入节点。

镜像树：将左子树和右子树的顺序调换，插入时右边为左，左边为右。

前序遍历：

对二叉排序树和镜像树分别进行前序遍历，记录结果。

比较输入序列与两棵树的前序结果，如果匹配则输出“YES”，否则输出“NO”。

方法二：利用后序遍历的反转

构建二叉排序树：

按照递增顺序插入节点。

后序遍历：

记录节点的后序访问顺序。

生成镜像树的前序序列：

将二叉排序树的后序结果反转，得到镜像树的前序序列。

比较：

输入序列与反转后的后序结果进行比较，若匹配则输出“YES”，否则输出“NO”。

代码实现

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct Node {    Node* lchild, *rchild;    int num;};vector
      
        inpVec;Node* create(int v) {    Node* root = new Node();    root->lchild = root->rchild = NULL;    root->num = v;    return root;}Node* insert1(Node* root, int v) {    if (!root) return create(v);    if (v < root->num) root->lchild = insert1(root->lchild, v);    else root->rchild = insert1(root->rchild, v);    return root;}Node* insert2(Node* root, int v) {    if (!root) return create(v);    if (v > root->num) root->lchild = insert2(root->lchild, v);    else root->rchild = insert2(root->rchild, v);    return root;}void preOrder(Node* root, vector
       
        & vec) {    vec.push_back(root->num);    if (root->lchild) preOrder(root->lchild, vec);    if (root->rchild) preOrder(root->rchild, vec);}int main() {    int n;    scanf("%d", &n);    Node* root1 = NULL, *root2 = NULL;    for (int i = 0; i < n; ++i) {        int k;        scanf("%d", &k);        inpVec.push_back(k);        root1 = insert1(root1, k);        root2 = insert2(root2, k);    }    vector
        
          preVec, mipreVec; preOrder(root1, preVec); preOrder(root2, mipreVec); if (inpVec == preVec) { printf("YES\n"); } else if (inpVec == mipreVec) { printf("YES\n"); } else { printf("NO\n"); } return 0;}