二叉搜索树与双向链表

题目：

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

		     4
		    /  \
		   2    5
          / \  
         1   3

则输出为:

解析：

剑指的解法稍微有点麻烦，本题使用容器vector求解。首先使用中序遍历把每一个节点放进vector容器中，最后把容器前后互相连接即可，话不多说，直接上代码，简单粗暴且易懂。

参考答案：

/***
*	typedef struct node{
*		int val;
*		struct node* left;
*		struct node* right;
*	}Node;
*/

class Solution{
public:
	vector<Node *> v;
	void helper(Node *root){
		if(nullptr == root)
			return;
			
		helper(root -> left);
		v.push_back(root);
		helper(root -> right);
	}
	
	Node* treeToDoublyList(Node* root){
		if(nullptr == root)
			return nullptr;
			
		helper(root);
		
		for(int i = 0; i < v.size() - 1; ++i){
			v[i] -> right = v[i + 1];
			v[i + 1] -> left = v[i]; 
		}
		
		v[0] -> left = v[v.size() - 1];
		v[v.size() - 1] -> right = v[0];

		return v[0]; 
	}
};