微软面试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}; 2.设计包含 min 函数的栈。定义栈的数据构造，规定添加一种 min 函数，可以得到栈的最小元素。规定函数 min、push 以及 pop 的时间复杂度都是 O(1)。 3.求子数组的最大和题目：输入一种整形数组，数组里有正数也有负数。数组中持续的一种或多种整数构成一种子数组，每个子数组均有一种和。求所有子数组的和的最大值。规定时间复杂度为 O(n)。例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2，因此输出为该子数组的和 18。 4.在二元树中找出和为某一值的所有途径题目：输入一种整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所通过的所有结点形成一条途径。打印出和与输入整数相等的所有途径。例如 输入整数 22 和如下二元树 10 / \ 5 12 / \ 4 7则打印出两条途径：10, 12 和 10, 5, 7。二元树节点的数据构造定义为：struct BinaryTreeNode // a node in the binary tree{int m_nValue; // value of nodeBinaryTreeNode *m_pLeft; // left child of nodeBinaryTreeNode *m_pRight; // right child of node}; 5.查找最小的 k 个元素题目：输入 n 个整数，输出其中最小的 k 个。例如输入 1，2，3，4，5，6，7 和 8 这 8 个数字，则最小的 4 个数字为 1，2，3 和 4。 第 6 题腾讯面试题： 给你 10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数 规定下排每个数都是先前上排那十个数在下排出现的次数。 上排的十个数如下： 【0，1，2，3，4，5，6，7，8，9】举一种例子， 数值: 0,1,2,3,4,5,6,7,8,9 分派: 6,2,1,0,0,0,1,0,0,0 0 在下排出现了 6 次，1 在下排出现了 2 次， 2 在下排出现了 1 次，3 在下排出现了 0 次.... 以此类推.. 第 7 题微软亚院之编程判断俩个链表与否相交给出俩个单向链表...
