牛客（JZ36 二叉搜索树与双向链表）

题目链接

思路1：使用中序遍历， 创建一个cur记录当前结点，prev记录上一个结点，这样cur->left = prev，prev->right = cur， 这样就链接 成功了。

难点：需要使用引用来控制prev。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/

//当前指针cur
//上一个结点prev
//cur->left = prev   //
//prec->right = cur 

class Solution {
public:
	// 得记录下上一层结点的地址，因此需要引用prev来记录
	void TreeToDLink(TreeNode* root, TreeNode*& prev)
	{
		if(root == nullptr)
		{
			return;
		}
		TreeToDLink(root->left, prev);
		TreeNode* cur = root;
		cur->left = prev;
		if(prev)    //第一次，prev是空
			prev->right = cur;
		prev = cur;
		TreeToDLink(root->right, prev);

	}

    TreeNode* Convert(TreeNode* pRootOfTree) {
		if(pRootOfTree == nullptr)
		{
			return nullptr;
		}
		TreeNode* prev = nullptr;
		TreeToDLink(pRootOfTree, prev);

		TreeNode* head = pRootOfTree;
		while(head->left != nullptr)
		{
			head = head->left;
		}
		return head;

    }
};