3.6 如何把二叉树转换为双向链表

难度系数：★★★☆☆　被考察系数：★★★★☆

题目描述：

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

分析与解答：

由于转换后的双向链表中结点的顺序与二叉树的中序遍历的顺序相同，因此，可以对二叉树的中序遍历算法进行修改，通过在中序遍历的过程中修改结点的指向来转换成一个排序的双向链表。实现思路如下图所示：假设当前遍历的结点为root，root的左子树已经被转换为双向链表（如下图（1）所示），使用两个变量pHead与pEnd分别指向链表的头结点与尾结点。那么在遍历root结点的时候，只需要将root结点的lchild指向pEnd，把pEnd的rchild （右）指向root；此时root结点就被加入到双向链表里了，因此，root变成了双向链表的尾结点，如图（2）所示。对于所有的结点都可以通过同样的方法来修改结点的指向。因此，可以采用递归的方法来求解，在求解的时候需要特别注意递归的结束条件以及边界情况（例如双向链表为空的时候）。

实现代码如下：

程序的运行结果为

算法性能分析：

这个算法与二叉树的中序遍历有着相同的时间复杂度O（n）。此外，这个算法只用了两个额外的变量pHead与pEnd来记录双向链表的首尾结点。因此，空间复杂度为O（1）。