题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
算法描述
使用递归，分别去将当前节点的左右子树变成双向链表，然后获取左边链表的最后一个元素，当前元素的左指针指向它，它的右指针指向当前元素；右边链表的第一个元素，它的左指针指向当前元素，当前元素的右指针指向它；然后从当前元素开始，不断从左边找，找到第一个元素，返回此元素的指针。
总结： 对这种涉及到二叉树的题目，可以使用测试驱动开始，先写测试用例，然后再编码。
代码实现#include <iostream>using std::cout;using std::cin;using std::endl;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){TreeNode* p = pRootOfTree;TreeNode* pl;TreeNode* pr;if( p != NULL ) {pl = Convert(p->left);pr = Convert(p->right);p->right= pr;if(pr){pr->left = p;}while(pl&&pl->right){pl = pl->right;}if(pl)pl->right= p;p->left= pl;while(p->left){p = p->left;}}return p;}};int main(){TreeNode* p1 = new TreeNode(1);TreeNode* p2 = new TreeNode(2);TreeNode* p3 = new TreeNode(3);TreeNode* p4 = new TreeNode(4);TreeNode* p5 = new TreeNode(5);TreeNode* p6 = new TreeNode(6);TreeNode* p7 = new TreeNode(7);p4->left = p2;p4->right= p6;p2->left = p1;p2->right= p3;p6->left= p5;p6->right= p7;Solution s;TreeNode* p = s.Convert(p4);while(p->right){cout<<p->val<<” “;p = p->right;}cout<<p->val<<” “;cout<<“\n”;while(p->left){cout<<p->val<<” “;p = p->left;}cout<<p->val<<” “;}
，总在盼望未来,愿你的人生美开
