题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
比如将二元查找树
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
思路：递归，在一时找不到递归的灵感的时候，多考虑考虑递归的参数，有时更重要的是考虑递归的返回值
每处理一个节点，首先获取左子树和右子树所返回的链表，然后拼接
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/* Problem: Convert a binary search tree into a sorted linkedlist */
/* When it comes to Tree-Structure, recursion is always the most common solution.
When designing recursion solution, should consider:
1. the parameters
2(important). the return object
*/
struct Node {
int value;
struct Node *left;
struct Node *right;
};
struct Node *
BTree2List(struct Node *root)
{
if(root == NULL)
return NULL;
struct Node *ret = NULL;
/* Convert the left tree into a sorted linkedlist */
struct Node *l_linkedlist = BTree2List(root->left);
ret = l_linkedlist==NULL ? root : l_linkedlist;
/* Convert the right tree into a sorted linkedlist */
struct Node *r_linkedlist = BTree2List(root->right);
while(l_linkedlist && l_linkedlist->right)
l_linkedlist = l_linkedlist->right;
/* Combine */
if(l_linkedlist)
l_linkedlist->right = root;
root->left = l_linkedlist;
root->right = r_linkedlist;
if(r_linkedlist)
r_linkedlist->left = root;
return ret;
}
int main(int argc, char** argv)
{
struct Node a = {4, NULL, NULL};
struct Node b = {8, NULL, NULL};
struct Node c = {12, NULL, NULL};
struct Node d = {16, NULL, NULL};
struct Node e = {6, NULL, &b};
struct Node f = {14, &c, NULL};
struct Node g = {10, &e, &f};
struct Node *ret = BTree2List(&g);
while(ret && ret->right) {
ret = ret->right;
}
while(ret) {
printf("%d\n", ret->value);
ret = ret->left;
}
return 0;
}