微软面试100题系列算法心得

浏览数：113 / 时间：2015年06月08日

谓之随笔，当是自己在练习此类算法的一些想法，一些心得，一些领悟，一些借鉴，当自引用之时，会附上相应的链接！

题：把二元查找树转变成排序的双向链表(树）

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

思维过程[个人思维]：

1. 二元查找树是指在任何结点看来，它的左子树上的值要少于当前结点的值，而它的右子树上的值要大于当前结点的值，对于等于的值那就看自己的原则放左子树还是右子树。

2. 关于树的算法必须要能够想到一些关键词：遍历算法[前序遍历、中序遍历、后序遍历、层次遍历]，算法复杂度O(logN)、O(1)、O(N)、O(NlogN),最常想到的是O(logN).递归算法及非递归算法[递归算法在树中应用最为广泛],各类树的特征及优势[常见的树有BST,AVL,B+-,堆，伸展树，线段树等],树的实现[静态实现,指针实现]，树结点信息[保存对应的信息有时候非常重要]

3. 看原题例子，可知此题核心是：中序遍历,用描述性的思维来说，左树先来，然后就是自己，然后再是右树。中序遍历常用递归实现，非递归较为烦琐

4. 联系题中要求，要排成一个双向链表，那么首先想到是中序遍历所有结点，返回中序遍历的序列，再连接成双向链表，需要细微注意的地方则是：头结点无前序结点，尾结点无后序结点。

下面则是对应的代码[有误请指证，感谢!]

BST树的定义：

1 struct Node{
2     Node * left;
3     Node * right;
4     int value;
5     Node() :left(NULL), right(NULL){}
6 };

中序遍历：

 1 vector<Node*> convert_doubledLinked(Node * root)
 2 {
 3     if (root == NULL) return vector<Node*>();
 4     auto l = convert_doubledLinked(root->left);
 5     auto r = convert_doubledLinked(root->right);
 6     l.push_back(root);
 7     for (const auto & v : r)
 8         l.push_back(v);
 9 
10     return l;
11 }

View Code

做链表并获取头结点：

 1 Node * get_head(vector<Node*> node_vector){
 2     if (node_vector.empty()) return NULL;
 3     Node * head = NULL;
 4     Node * prev = NULL;
 5 
 6     for (auto & v : node_vector){
 7         if (head == NULL)
 8             head = v;
 9 
10         if (head != v){
11             prev->right = v;
12             v->left = prev;
13         }
14 
15         prev = v;
16         v->right = NULL;
17     }
18     head->left = NULL;
19     return head;
20 }

View Code

5. 当然我们可能更想不分成两部分做，想将其合并在一个递归里，如此首先要明白是当前结点在双向链表中的前序结点是哪一个，当前结点的后序结点又是哪一个，不难想到，前序结点是左子树中最后遍历的结点，描述性的说：在当前结点的左子树中一直往右走，走到尽头的那个点便是，后序结点是右子树中最先遍历的点，描述性的说：在当前结点的右子树中一直往左走，走到尽头的那个结点。我们有多种方法得到这两个值，譬如按定义去找，譬如把子树连接成双向链表，便可知一切。有时候想一想，只需要我们所需要的信息即可，希望左子树给我前序的结点，右子树给我后序的结点，思索着，我希望子树递归完后，它能给我最左边的结点与最右边的结点，如此递归函数附加两个引用返回值则可，当然，我也可以利用每个结点恰好能保存两个结点，而把这两个参数合并为一个。

代码如下：

 1 Node * convert_doubledLinked(Node * root, Node &data){
 2     if (root == NULL){
 3         data.left = NULL;
 4         data.right = NULL;
 5         return root;
 6     }
 7 
 8     Node ta, tb;
 9 
10     Node * l = convert_doubledLinked(root->left, ta);
11     Node * r = convert_doubledLinked(root->right, tb);
12 
13     if (ta.right != NULL){
14         ta.right->right = root;
15         root->left = ta.right;
16     }
17     if (tb.left != NULL){
18         root->right = tb.left;
19         tb.left->left = root;
20     }
21 
22     data.left = (ta.left == NULL) ? root : ta.left;
23     data.right= (tb.right == NULL)? root: tb.right;
24 
25     return data.left;
26 }