70道常见面试算法笔试题

《70道常见面试算法笔试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、微软等面试100题答案1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10//614////481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//ri

2、ghtchildofnode};//引用245楼tree_star的回复#include#includestructBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};typedefBSTreeNodeDoubleList;DoubleList*pHead;DoubleList*pLi

3、stIndex;voidconvertToDoubleList(BSTreeNode*pCurrent);//创建二元查找树voidaddBSTreeNode(BSTreeNode*&pCurrent,intvalue){if(NULL==pCurrent){BSTreeNode*pBSTree=newBSTreeNode();pBSTree->m_pLeft=NULL;pBSTree->m_pRight=NULL;pBSTree->m_nValue=value;pCurrent=pBSTree

4、;}else{if((pCurrent->m_nValue)>value){addBSTreeNode(pCurrent->m_pLeft,value);}elseif((pCurrent->m_nValue)m_pRight,value);}else{//cout<<"重复加入节点"<

5、nt){return;}if(NULL!=pCurrent->m_pLeft){ergodicBSTree(pCurrent->m_pLeft);}//节点接到链表尾部convertToDoubleList(pCurrent);//右子树为空if(NULL!=pCurrent->m_pRight){ergodicBSTree(pCurrent->m_pRight);}}//二叉树转换成listvoidconvertToDoubleList(BSTreeNode*pCurrent){pCurren

6、t->m_pLeft=pListIndex;if(NULL!=pListIndex){pListIndex->m_pRight=pCurrent;}else{pHead=pCurrent;}pListIndex=pCurrent;cout<m_nValue<

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

8、ntinue//////////////////////////////////////////////--------------------------------------------------------------同样是上道题，给各位看一段简洁的代码，领悟一下c的高效与美：voidchange(Node*p,Node*&last)//中序遍历{if(!p)return;change(p->left,last);if(last)last->right=p;p->left=last;l