华为机试题: 二叉搜索树 你的名字 2022-08-20 05:24 87阅读 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)"> 描述: </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)"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 判断两序列是否为同一二叉搜索树序列</p> </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)"> 树 </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)"> 中级 </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)"> 入职前练习 </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)"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> </p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> </p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> </p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> </p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> </p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> </p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。</p> </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)"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 如果序列相同则输出YES,否则输出NO</p> </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; }
还没有评论,来说两句吧...