题解 | #二叉搜索树与双向链表#

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	//
	void InOrder(TreeNode* root,TreeNode*& prev)
	{
		if(root == nullptr)
		return;

		InOrder(root->left,prev);
		root->left = prev;
		if(prev)
		prev->right = root;
		prev = root;

		InOrder(root->right,prev);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr;

		if(pRootOfTree == nullptr)
		return nullptr;
		InOrder(pRootOfTree,prev);

		TreeNode* cur = pRootOfTree;
		while(cur->left)
		{
			cur = cur->left;
		}
		return cur;
    }
};

通过中序遍历，来修改结点的指向。因为要求的双向链表是升序的，所以二叉树 改为 双向链表后，修改时有以下特点：

1.修改二叉树的left为前驱

2.修改二叉树的right为后继

在一层递归中：

修改二叉树的left为前驱：root->left = prev

修改二叉树的right为后继：由于下一个结点未知，所以不知道后继为哪一个结点。但是可以通过prev修改上一层结点的后继。

因此prev->right = root

最后，通过根结点找到头结点。返回即可