題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。
比如將二元查找樹
10
/ \
6 14
/ \ / \
4 8 12 16
轉(zhuǎn)換成雙向鏈表
4=6=8=10=12=14=16。
思路：遞歸，在一時找不到遞歸的靈感的時候，多考慮考慮遞歸的參數(shù)，有時更重要的是考慮遞歸的返回值
每處理一個節(jié)點，首先獲取左子樹和右子樹所返回的鏈表，然后拼接
代碼：
#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;
}