微软等公司数据结构+算法面试100 前40(附答案).pdf

《微软等公司数据结构+算法面试100 前40(附答案).pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/614//481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};//引用245楼tree_star的回复#include#i

2、ncludestructBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};typedefBSTreeNodeDoubleList;DoubleList*pHead;DoubleList*pListIndex;voidconvertToDoubleList(BSTreeNode*pCurrent);//创建二元查找树voidaddBSTreeNode(BSTreeNode*&pCurren

3、t,intvalue){if(NULL==pCurrent){BSTreeNode*pBSTree=newBSTreeNode();2pBSTree->m_pLeft=NULL;pBSTree->m_pRight=NULL;pBSTree->m_nValue=value;pCurrent=pBSTree;}else{if((pCurrent->m_nValue)>value){addBSTreeNode(pCurrent->m_pLeft,value);}elseif((pCurrent->m_nValue)m_pRi

4、ght,value);}else{//cout<<"重复加入节点"<m_pLeft){ergodicBSTree(pCurrent->m_pLeft);}//节点接到链表尾部convertToDoubleList(pCurrent);//右子树为空if(NULL!=pCurrent->m_pRight){ergodicBSTree(pCurrent->m_pRight);}}

5、3//二叉树转换成listvoidconvertToDoubleList(BSTreeNode*pCurrent){pCurrent->m_pLeft=pListIndex;if(NULL!=pListIndex){pListIndex->m_pRight=pCurrent;}else{pHead=pCurrent;}pListIndex=pCurrent;cout<m_nValue<

6、;addBSTreeNode(pRoot,4);addBSTreeNode(pRoot,6);addBSTreeNode(pRoot,8);addBSTreeNode(pRoot,12);addBSTreeNode(pRoot,14);addBSTreeNode(pRoot,15);addBSTreeNode(pRoot,16);ergodicBSTree(pRoot);return0;}///////////////////////////////////////////////4681012141516Pressanykeytocontinue/////////////////

7、/////////////////////////////42.设计包含min函数的栈。定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。结合链表一起做。首先我做插入以下数字：10，7，3，3，8，5，2，60:10->NULL(MIN=10,POS=0)1:7->[0](MIN=7,POS=1)用数组表示堆栈，第0个元素表示栈底2:3->[1](MIN=3,POS=2)3:3->[2](MIN