最近找工作看到了一篇数据结构与算法题的结构的面试题集合觉得还不错，正好这方面是自己的弱点，正好现在开始补一补。数据结构与算法面试题80道

下面从第一题开始一道一道开始撸

1.把二元查找树转变成排序的双向链表

题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。

   10
 / \
 6 14
 / \ / \
4 8 12 16

转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树 节点的数据结构如下：

 struct BSTreeNode
{
 int m_nValue; // value of node
 BSTreeNode *m_pLeft; // left child of node
 BSTreeNode *m_pRight; // right child of node
};

据说这是微软面试题，像这种有关树的题基本上都需要用到递归算法
解题思路：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode -           the head of the sub tree
//        pLastNodeInList - the tail of the double-linked list
///////////////////////////////////////////////////////////////////////
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
      if(pNode == NULL)
            return;
    //   获取当前的节点
      BSTreeNode *pCurrent = pNode;

      // Convert the left sub-tree
    //   如果有做节点就递归遍历左节点
      if (pCurrent->m_pLeft != NULL)
            ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

      // Put the current node into the double-linked list
    //   如果没有左节点就把已经排序好的链表放到当前节点的左节点
    // 通俗的说就是把当前节点排到链表的末尾
      pCurrent->m_pLeft = pLastNodeInList; 
      if(pLastNodeInList != NULL)
            pLastNodeInList->m_pRight = pCurrent;//双向链表要把右节点也填上
    // 把指针挪到了链表的未结点
      pLastNodeInList = pCurrent;

      // Convert the right sub-tree
      //如果右节点的话接着递归进行中序遍历
      if (pCurrent->m_pRight != NULL)
            ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
{
    //初始化一个空的链表 作为结果
      BSTreeNode *pLastNodeInList = NULL;
      ConvertNode(pHeadOfTree, pLastNodeInList);

      // Get the head of the double-linked list
      BSTreeNode *pHeadOfList = pLastNodeInList;
      while(pHeadOfList && pHeadOfList->m_pLeft)
            pHeadOfList = pHeadOfList->m_pLeft;

      return pHeadOfList;
}

具体的已经写注释啦 递归的特点就是代码简单，但是理解起来比较复杂

2.定义栈的数据结构， 要求添加一个 min 函数， 能够得到栈的最小元素。 要求函数 min、 push 以及 pop 的时间复杂度都是 O(1)

刚开始解这道题目的时候，感觉不是很难，只需在栈的数据结构中加一个选项min就OK了，这样就可以记录最小值。但是这个思路有一个硬伤，那就是第一次调用min函数时，是可以直接获取到最小值，但是如果调用pop()函数将最小值出栈过后，再给min赋值时，就需要进行查找比较了，那样就不满足题目要求，min函数的复杂度为1. 既然如此，那我们是否可以记录下每push进一个数据时当前的min值，每一次发生变化就将当前的min值压入到一个数组中，这样就可以解决上述问题。因此这道题目的难点我认为就是数组设计是否合理。
设计了以下的数组结构：
源程序如下：

#include<iostream>
using namespace std;

#define MAXSIZE 100

typedef int ElemType;

struct Stack{
    int top;//当前栈顶位置
    int index;//当前最小min位置
    ElemType data[MAXSIZE];//存储栈的数据
    ElemType minData[MAXSIZE];//存储最小值的合集
    int min;//记录最小值（预留）
};

//初始化栈
bool InitStack(Stack* ptr){
    ptr->top = 0;
    ptr->index = 0;
    ptr->min = 0;

    return true;
}

bool push(Stack* ptr, ElemType elem){
    //首先需要判断栈是否已满
    if(MAXSIZE-1 == ptr->top){
        cout << "Stack is full, cannot push data anymore!" << endl;
        return false;
    }
    //判断是否是第一个压入栈的数据,将最小值存储到minStack中
    if(0 == ptr->top){
        // 第一个数据直接赋值成最小值
        ptr->min = elem;
        // 注意此处是后++  计算完再++
        ptr->minData[ptr->index++] = elem;
    } else if(elem <= ptr->min){//如果入栈的数据比当前最小值小
        ptr->min = elem;
        // 最小值如果更改了就把更改状态的值存进去，里面的数值可能是重复的
        ptr->minData[ptr->index++] = ptr->min;
    }
    // 把值存到数据的栈的数组中
    ptr->data[(ptr->top)++] = elem;

    return true;
}

ElemType pop(Stack* ptr, ElemType* elem){
    //判断栈是否为空
    if(0 == ptr->top){
        cout << "stack is empty, cannot pop data anymore!" << endl;
        return -65535;
    }
    // 因为push的时候已经进行了后++ ，所以此处想获取当前的位置就先--
    *elem = ptr->data[--(ptr->top)];

    int i = ptr->index - 1;
    if(*elem == ptr->minData[i]){
        --(ptr->index);
    }

    return *elem;
}

ElemType minMethod(Stack* ptr){
    // 此处维护了一个数组，所以时间复杂度为1
    return ptr->minData[--(ptr->index)];
}
// data 5,4,4,4
// min  5,4,4,4

int main() {
    Stack ptr;
    int elem;
    // 初始化栈
    InitStack(&ptr);
    push(&ptr, 5);
    push(&ptr, 4);
    push(&ptr, 4);
    push(&ptr, 4);
//  cout << "pop1: " << pop(&ptr, &elem) << endl;
//  push(&ptr, 8);
    pop(&ptr, &elem);
    pop(&ptr, &elem);
    pop(&ptr, &elem);
//  cout << "pop2: " << pop(&ptr, &elem) << endl;
    cout << "minMethod: " << minMethod(&ptr) << endl;

    return 0;
}