二叉搜索树与双向链表
C++，中序遍历构造链表，类似于线索二叉树。
既然要生成一个有序的链表，那就应该很快想到中序遍历。
方法如下：
- 首先中序遍历整棵树，可以得到key小的结点一定比key大的结点先访问；
- 需要同时能操作第k个被访问的结点和第k+1个被访问的结点，这样才能在前后两个结点之间建立关系；
- 也就是让第k个结点的right指向第k+1个结点，让第k+1个结点的left指向第k个结点；
- 根据中序遍历的特点，左中右，左儿子一定比根结点先遍历，右儿子一定比根结点后遍历；
- 为了在遍历到根结点时，能同时处理和左子树中前一个结点的关系，需要用到引用传递；
- 为了在遍历到右儿子时，能同时处理右儿子与父结点的关系，直接把父结点传入中序遍历函数就行；
- 所以函数声明应该为
inorder(TreeNode *root, TreeNode *&pre)； - 理解了这个逻辑，思路就很简单了。
代码如下：
/*
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) return nullptr;
TreeNode *pre = nullptr;
Inorder(pRootOfTree, pre);
TreeNode *head = pRootOfTree;
while (head->left)
head = head->left;
return head;
}
void Inorder(TreeNode *root, TreeNode *&pre) {
if (!root)
return ;
Inorder(root->left, pre);
root->left = pre;
if (pre) pre->right = root;
pre = root;
Inorder(root->right, pre);
}
};
