【剑指Offer】二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

算法描述

使用递归，分别去将当前节点的左右子树变成双向链表，然后获取左边链表的最后一个元素，当前元素的左指针指向它，它的右指针指向当前元素；右边链表的第一个元素，它的左指针指向当前元素，当前元素的右指针指向它；然后从当前元素开始，不断从左边找，找到第一个元素，返回此元素的指针。

总结：
对这种涉及到二叉树的题目，可以使用测试驱动开始，先写测试用例，然后再编码。

代码实现

#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<<" ";
	 
}