题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。比如，输入下图中左边的二叉搜索树，则输出转换之后的排序双向链表。
树节点的定义如下:
题目分析
在二叉树中，每个节点都有两个指向子节点的指针。在双向链表中，每个节点也有两个指针，分别指向前一个节点和后一个节点。由于这两种节点的结构相似，同时二叉搜索树也是一种排序的数据结构，因此，在理论上有可能实现二叉搜索树和排序双向链表的转换。在搜索二叉树中，左子节点的值总是小于父节点的值，右子节点的值总是大于父节点的值。因此，我们在将二叉搜索树转换成排序双向链表时，原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。接下来我们考虑该如何转换。
由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每个节点，这是因为中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每个节点。当遍历到根节点的时候，我们把树看成3部分:值为10的节点;根节点值为6的左子树;根节点值为14的右子树。根据排序链表的定义值为10的节点将和它的左子树的最大一个节点(值为8的节点)链接起来，同时它还将和右子树最小的节点(值为12的节点)链接起来，如下图所示。
按照中序遍历的顺序，当我们遍历转换到根节点(值为10的节点)时，它的左子树已经转换成一个排序的链表了，并且处在链表中的最后一个节点是当前值最大的节点。我们把值为8的节点和根节点链接起来，此时链表中的最后一个节点就是10了。接着我们去遍历转换右子树，并把根节点和右子树中最小的节点链接起来。至于怎么去转换它的左子树和右子树,由于遍历和转换过程是一样的，我们很自然地想到可以用递归。
代码实现
代码解释
在上面的代码中，我们用 pLastNodeInList 指向已经转换好的链表的最后一个节点(值最大的节点)。当我们遍历到值为10的节点的时候，它的左子树都已经转换好了，因此pLastNodeInList指向值为8的节点。接着把根节点链接到链表中之后，值为10的节点成了链表中的最后一个节点(新的值最大的节点)，于是 pLastNodeInList 指向了这个值为 10 的节点。接下来把 pLastNodeInList 作为参数传入函数递归遍历右子树。我们找到右子树中最左边的子节点(值为12的节点，在右子树中值最小)，并把该节点和值为 10 的节点链接起来。
测试用例
功能测试(输入的二叉树是完全二叉树;所有节点都没有左/右子树的二叉树;只有一个节点的二叉树)。
特殊输入测试(指向二叉树根节点的指针为 nullptr 指针)。
本题考点
考查应聘者分析复杂问题的能力。无论是二叉树还是双向链表，都有很多指针。要实现这两种不同数据结构的转换，需要调整大量的指针，因此这个过程会很复杂。为了把这个复杂的问题分析清楚，我们可以把树分为3部分:根节点、左子树和右子树，然后把左子树中最大的节点、根节点、右子树中最小的节点链接起来。至于如何把左子树和右子树内部的节点链接成链表,那和原来的问题的实质是一样的，因此可以递归解决。解决这个问题的关键在于把一个大的问题分解成几个小问题，并递归地解决小问题。
考查应聘者对二叉树和双向链表的理解及编程能力。