本文共 1333 字，大约阅读时间需要 4 分钟。
Q：输入一颗二叉搜索树，将该二叉搜索树转换为一个排序的双向链表。要求不能创建任何新的结点。
分析：二叉搜索树的中序遍历就是一个有序的序列，而树的左孩子指针和有孩子指针当然就充当了前驱和后继指针，所以这种转换是自然的。
我们定义结构体如下：
struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int v) : val(v),left(0),right(0){}}; 回想中序遍历的模板: void InOrderVisit(TreeNode *root){ if(!root) return; InOrderVisit(root->left); visit(root); InOrderVisit(root->right);} 该题目中，visit函数显然不是仅仅打印出这个值这么简单，但其实质还是一样的，既然中序访问各个节点的顺序是有序的，那么我们只需要将访问到的结点挂在到一个双向链表上就可以，想想我们创建一个双向链表的过程，在链表的表尾，创建新的结点，将其与表尾的结点连接，由于不允许我们使用额外的结点，所以这里就要求我们判断链表头结点是否为空的情况。若没有这个限制，像我们在进行链表的操作的时候，为了统一操作，我们总是会创建一个只起到统一操作的表头节点，其中不包含任何有用信息。 那么现在我们设计下我们程序的大体流程，以及需要哪些参数。
首先，我们要不停的修改双向链表，所以要有一个二级指针，或者是一级指针的引用，这里我们选择使用引用&。
接下来，在visit功能块里，我们把访问的结点挂到链表的表尾。
因为是双向的，所以即使我们只记录链表尾结点，通过循环向前寻找，我们是可以得到链表的表头的。
void TreeToLink(TreeNode *root,TreeNode *&linkTail){ if(!root) return ; //handle its left_sub_tree TreeToLink(root->left,linkTail); //similar to visit() //handle the first node if(linkTail == NULL) linkTail = root; else { linkTail->right = root; root->left = linkTail; linkTail = root; } //handle its right_sub_tree TreeToLink(root->right,linkTail);} 最终，我们得到的linkTail是一个尾结点，我们可以通过left指针域向前遍历，得到头，至此，问题就解决了。 总结：
这类的问题很多，但都有一个共性，就是他们都是三种递归遍历的变种，不同的是visit的处理，但都可以套用模板。
参考书里给出的解法也不错，但个人觉得有点麻烦，既然有模板，我们还是推荐套用模板，就像我们高考时的作文，自己熟练掌握几套模板总是很受用的，所谓万变不离其踪。
转载地址：http://wglji.baihongyu.com/