华为机试题：二叉搜索树

你的名字 2022-08-20 05:24 112阅读 0赞

<table style="margin:0px; padding:0px; width:970px; border:0px; border-collapse:collapse; border-spacing:0px; empty-cells:show; color:rgb(0,0,0); font-family:'Times New Roman',Arial,微软雅黑,宋体,Tahoma,Helvetica,SimSun,sans-serif,宋体"> 
 <tbody style="margin:0px; padding:0px"> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 描述:&nbsp;</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 判断两序列是否为同一二叉搜索树序列 &nbsp;</td> 
 </tr> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 题目类别:</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> &nbsp;树&nbsp;</td> 
 </tr> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 难度:</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> &nbsp;中级&nbsp;</td> 
 </tr> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 运行时间限制:</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 10Sec</td> 
 </tr> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 内存限制:</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 128MByte</td> 
 </tr> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 阶段:</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> &nbsp;入职前练习&nbsp;</td> 
 </tr> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 输入:</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> &nbsp; 开始一个数n，(1&lt;=n&lt;=20)&nbsp;表示有n个需要判断，n=&nbsp;0&nbsp;的时候输入结束。 &nbsp; &nbsp; &nbsp; 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。 &nbsp; &nbsp; &nbsp; 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。 &nbsp;</td> 
 </tr> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 输出:</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> &nbsp; 如果序列相同则输出YES，否则输出NO &nbsp;</td> 
 </tr> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 样例输入:</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px; white-space:pre-wrap; word-wrap:break-word; line-height:24px">2
567432
543267
576342
0
 </pre> </td> 
 </tr> 
 <tr style="margin:0px; padding:0px; height:26px"> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; border-right-style:solid; border-right-width:1px; border-right-color:rgb(238,238,238); font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> 样例输出:</td> 
 <td style="margin:0px; padding:6px 3px 3px; word-break:break-all; word-wrap:break-word; font-size:14px; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:rgb(238,238,238)"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px; white-space:pre-wrap; word-wrap:break-word; line-height:24px">YES
NO
 </pre> </td> 
 </tr> 
 </tbody> 
</table>

#include <iostream>
 #include <stdio.h>
 #include <string>
 #include <algorithm>
 #include <map>
 #include <vector>
 
 using namespace std;
 
 typedef struct Node
 {
 char data;
 struct Node* lchild;
 struct Node* rchild;
 
 /*构造函数*/
 Node(char d):data(d),lchild(NULL),rchild(NULL)
 {
 
 }
 }NODE;
 
 void InsertBiTreeNode(NODE* &root, char val)
 {
 NODE* pNewNode = new NODE(val);
 
 /*如果是一个空树*/
 if(root == NULL)
 {
 root = pNewNode;
 return;
 }
 
 NODE* p = root, *pre = NULL;
 
 /*找到插入的节点*/
 while(p)
 {
 pre = p;
 if(p->data < val)
 {
 p = p->rchild;
 }
 else
 {
 p = p->lchild;
 }
 }
 
 /*将该节点插入*/
 if(pre->data > val)
 {
 pre->lchild = pNewNode;
 }
 else
 {
 pre->rchild = pNewNode;
 }
 
 return;
 }
 
 /*构建线索二叉树*/
 NODE* createBiTree(string str)
 {
 int i = 0, lens = str.size();
 NODE* root = NULL;
 
 for(i = 0; i < lens; i++)
 {
 InsertBiTreeNode(root,str[i]);
 }
 
 return root;
 }
 
 /*前序遍历二叉树*/
 void preTree(NODE* root, string &ret)
 {
 if(root == NULL)
 {
 return;
 }
 ret += root->data;
 preTree(root->lchild,ret);
 preTree(root->rchild,ret);
 }
 int main()
 {
 int n = 0;
 
 while(cin >> n && n != 0)
 {
 string str,ret1;
 NODE* root1 = NULL;
 
 cin >> str;
 root1 = createBiTree(str);
 preTree(root1,ret1);
 
 while(n--)
 {
 cin >> str;
 
 NODE* pTree = NULL;
 pTree = createBiTree(str);
 
 string ret2;
 preTree(pTree,ret2);
 
 if(ret1 == ret2)
 {
 cout << "YES" << endl;
 }
 else
 {
 cout << "NO" << endl;
 }
 }
 }
 
 return 0;
 }