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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	TreeNode* head = nullptr;
	TreeNode* tail = nullptr;
    TreeNode* Convert(TreeNode* cur) {
        if (cur == nullptr) return nullptr;

		// 中序遍历: 左 中 右		
		Convert(cur->left);
		// 第1次开始转换，确定链表头节点
		if (tail == nullptr) {
			head = cur;
			tail = cur;
		} else {
			tail->right = cur; // 尾节点右指针指向当前节点cur
			cur->left = tail;  // 当前节点cur的左指针指向尾部节点
			tail = cur;  	   // 尾部节点更新到当前节点
		}
		Convert(cur->right);
		return head;		
    }
};