题目描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
分析：
二叉搜索树，中序遍历就是排序的。
所以我们利用中序遍历，将前后两个结点连接在一起。
不过为了方便起见，我们可以用中序遍历的逆过程，最后遍历到最小的结点，并连接它，也可以输出为链表的首结点。
我们需要两个指针，记录一前一后的结点。
代码：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree) {
if(pRootOfTree == NULL) return NULL;
if(pRootOfTree->left == NULL && pRootOfTree->right == NULL) return pRootOfTree;
TreeNode* pHead = NULL;
RDL(pRootOfTree, pHead);
return pHead;
} void RDL(TreeNode* pRootOfTree, TreeNode* &pHead) { // 中序遍历的逆过程
if(pRootOfTree == NULL) return;
if(pRootOfTree->right) {
RDL(pRootOfTree->right, pHead); // 右递归
}
pRootOfTree->right = pHead; // 连接后一个结点
if(pHead != NULL) { // 连接前一个结点
pHead->left = pRootOfTree;
}
pHead = pRootOfTree; // pHead前移
if(pRootOfTree->left) {
RDL(pRootOfTree->left, pHead); // 左递归
}
}
};