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
};

答案：void change(Node *p, Node *&last) //中序遍历 

{ 

 if (!p) 

  return; 

 change(p->left, last); 

 if (last) 

  last->right = p; 

 p->left = last; 

 last = p; 

 change(p->right, last); 

} 

void main() 

{ 

 Node *root = create(); 

 Node *tail = NULL; 

 change(root, tail); 

 while (tail) 

 { 

  cout << tail->data << " "; 

  tail = tail->left; 

 } 

 cout << endl; 

}  

2.求子数组的最大和（数组）
题目：
输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

之前上传的答案是：
int maxSum(int* a, int n)
{
 int sum=0;  int b=0;
 for(int i=0; i<n; i++)
 {   
  if(b<0)     
   b=a[i];   
  else    
   b+=a[i];  
  if(sum<b)    
   sum=b;
 }
 return sum;
}

答案：int get_sub_sum_max(int *arr, int len)
{
 int max, sum;
 
 max = arr[0];
 sum = 0;
 while (len--)
 {
  sum += *arr++;
 
  if (sum > max)
   max = sum;
  else if (sum < 0)
   sum = 0;
 }

 return max;
}

3.数组
腾讯面试题：
给你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次....

答案分析：说实话，这题除了一次次迭代尝试外，我没想到什么好的处理办法。假设上排的数组为a，下排对应的数组为b，元素个数为n，按照题目的意思可以得到以下公式：
b1+b2+...+bn=na1*b1+a2*b2+...+an*bn=nb
中的元素来源于a这种一次多项表达式的求解我不会。

我觉得这题比实际上还要复杂，以下情况是必须要考虑的：
1、上排的数据元素并不一定是排序的。
2、上排的数据元素并不一定就有0，可能还有负数。
3、上排的数据元素可能会有重复的。
4、未必有对应的下排数据。

除了上面提到的，就楼主的程序而言，个人觉得有以下几个改进建议：
1、类中success是个多余的东西，如果设置这么一个成员变量，就不应该在函数setNextBottom中再无谓多一个reB变量。
2、由于未必有解，getBottom可能限于死循环。
3、getBottom中变量i完全是多余的。
4、getFrequecy中判断有些是多余的，可以考虑把我上面提到的公司考虑进去。

等有时间了，我再好好考虑如何写个比较好的程序。

4.链表
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。

问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
答案分析：如果不需要求出两个链表相交的第一个节点，楼主提出的方法挺好的。
如果需要求出相交第一个节点，我有以下思路：
以链表节点地址为值，遍历第一个链表，使用Hash保存所有节点地址值，结束条件为到最后一个节点（无环）或Hash中该地址值已经存在（有环）。再遍历第二个链表，判断节点地址值是否已经存在于上面创建的Hash表中。

这个方面可以解决题目中的所有情况，时间复杂度为O(m+n)，m和n分别是两个链表中节点数量。由于节点地址指针就是一个整型，假设链表都是在堆中动态创建的，可以使用堆的起始地址作为偏移量，以地址减去这个偏移量作为Hash函数。

5.树
判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

         8
      /  /
     6    10
    / /  / /
   5  7 9  11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。

答案：
int is_post_traverse(int *arr, int len)
{
 int *head, *pos, *p;
 
 if (arr == NULL || len <= 0)
  return 0;
 if (len == 1)
  return 1;
 
 head = arr + len - 1;
 p = arr;
 while (*p < *head)
  p++;
 pos = p;
 
 while (p < head)
 {
  if (*p < *head)
   return 0;
  p++;
 }
 
 if (!is_post_traverse(arr, pos - arr))
  return 0;
 return is_post_traverse(pos, head - pos);
}

6.链表：
题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
  int m_nKey;
  ListNode* m_pNext;
};

答案：       list *list_find_desc(list *head, int k)
      {
                list *p, *q;

        if (head == NULL || k < 0)
                return NULL;

        p = head;
        while (p != NULL && k-- >= 0)
        {
                p = p->next;
        }
        if (p == NULL)
                return k < 0 ? head : NULL;
      
        q = head;
        while (p != NULL)
        {
                p = p->next;
                q = q->next;
        }
      
        return q;
}