首页 > 代码库 > 微软面试100题系列算法心得
微软面试100题系列算法心得
微软100题系列地址
答案地址
谓之随笔，当是自己在练习此类算法的一些想法，一些心得，一些领悟，一些借鉴，当自引用之时，会附上相应的链接！
题：把二元查找树转变成排序的双向链表(树）
描述：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
思维过程[个人思维]：
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 }
做链表并获取头结点：
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 }
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 }
微软面试100题系列算法心得