题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
1 /* 2 struct TreeNode { 3 int val; 4 struct TreeNode *left; 5 struct TreeNode *right; 6 TreeNode(int x) : 7 val(x), left(NULL), right(NULL) { 8 } 9 };*/10 class Solution {11 public:12 TreeNode* Convert(TreeNode* pRootOfTree)13 {14 if(pRootOfTree==NULL) return NULL;15 TreeNode* head=pRootOfTree;16 TreeNode* tail=NULL;17 converttree(head,&tail);18 while(head->left!=NULL)19 head=head->left;20 return head;21 22 }23 private:24 void converttree(TreeNode* root,TreeNode** tail){25 if(root==NULL)26 return;27 TreeNode* tmp=root;28 if(root->left!=NULL){29 converttree(root->left,tail);30 }31 root->left=*tail;32 if((*tail)!=NULL)33 (*tail)->right=tmp;34 *tail=tmp;35 if(tmp->right!=NULL)36 converttree(tmp->right,tail);37 }38 }; 转自：
题目描述：
-
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
- 输入：
-
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数n(0<n<1000)，代表测试样例的个数。接下来的n行，每行为一个二叉搜索树的先序遍历序列，其中左右子树若为空则用0代替。
- 输出：
-
对应每个测试案例，
输出将二叉搜索树转换成排序的双向链表后，从链表头至链表尾的遍历结果。
- 样例输入：
12 1 0 0 3 0 0
- 样例输出：
1 2 3
1 void createTree(BTree **b){ 2 int m; 3 scanf("%d",&m); 4 if(m == 0) 5 *b = NULL; 6 else{ 7 BTree *s = (BTree *)malloc(sizeof(BTree)); 8 s->data = m; 9 s->lchild = NULL;10 s->rchild = NULL;11 *b = s;12 createTree(&((*b)->lchild));13 createTree(&((*b)->rchild));14 }15 } 另外，整体的思路，是用一个指针记录转换的双链表表尾。
每次进行中序遍历的转换。
最先转换的是最左下的节点，
1 void converNode(BTree *b,BTree **p){ 2 if(b == NULL) 3 return ; 4 BTree *pnow = b; 5 if(b->lchild != NULL) 6 converNode(b->lchild,p); 7 8 pnow->lchild = *p; 9 if(*p != NULL)10 (*p)->rchild = pnow;11 12 *p = pnow;13 14 if(b->rchild != NULL)15 converNode(b->rchild,p);16 } 每次遍历节点的左孩子右孩子。把左孩子指向转换链表的尾节点，并把末尾指针的右孩子指向自己。右孩子指向节点的右孩子。如果没有右孩子就返回。下面是代码思路的步骤：
1 找到最左边也就是最小的节点，PLast = NULL;
2 让节点的左孩子指向链尾，然后链尾指针右移。如果右孩子为空就返回。
最后我们从尾遍历回头指针返回。
全部代码：
1 #include2 #include 3 typedef struct btree{ 4 int data; 5 struct btree *lchild,*rchild; 6 }BTree; 7 8 void createTree(BTree **b); 9 void inorderTree(BTree *b);10 BTree * convert(BTree *b);11 void converNode(BTree *b,BTree **p);12 13 int main(){14 int n;15 scanf("%d",&n);16 while(n--){17 BTree *b = (BTree *)malloc(sizeof(BTree)); 18 createTree(&b);19 BTree *head = convert(b);20 while(head!=NULL){21 printf("%d ",head->data);22 head = head->rchild;23 }24 printf("\n");25 }26 return 0;27 }28 BTree* convert(BTree *b){29 BTree *pLast = NULL;30 converNode(b,&pLast);31 32 BTree *phead = pLast;33 while(phead != NULL && phead->lchild != NULL)34 phead = phead->lchild;35 return phead;36 }37 void converNode(BTree *b,BTree **p){38 if(b == NULL)39 return ;40 BTree *pnow = b;41 if(b->lchild != NULL)42 converNode(b->lchild,p);43 44 pnow->lchild = *p;45 if(*p != NULL)46 (*p)->rchild = pnow;47 48 *p = pnow;49 50 if(b->rchild != NULL)51 converNode(b->rchild,p);52 }53 void createTree(BTree **b){ 54 int m;55 scanf("%d",&m);56 if(m == 0)57 *b = NULL;58 else{59 BTree *s = (BTree *)malloc(sizeof(BTree));60 s->data = m;61 s->lchild = NULL;62 s->rchild = NULL;63 *b = s;64 createTree(&((*b)->lchild));65 createTree(&((*b)->rchild));66 }67 }68 /**************************************************************69 Problem: 150370 User: xhalo71 Language: C72 Result: Accepted73 Time:80 ms74 Memory:1704 kb75 ****************************************************************/
解题思路：
这道题应该是最近写的最繁琐的一道题了。
首先输入按规则来，需要进行前序遍历输入