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

基本思路：

• 二叉搜索树要转换成排序链表，必然是左中右的中序遍历
• 函数返回值是双向链表的头节点，而每次遍历节点需要的是当前节点中序遍历下的先驱节点，所以需要一个额外指针bef记录先驱节点
• 先按照左中右的遍历顺序遍历左子树，然后将先驱节点与当前节点连接，此时需要遍历右子树了，所以需要让先驱节点指向当前节点，再遍历右子树
• 处理边界问题

class Solution {
public:
	TreeNode* bef = nullptr;

    TreeNode* Convert(TreeNode* pRootOfTree) {
        if (!pRootOfTree) return nullptr;
		TreeNode* l = Convert(pRootOfTree->left), *r = pRootOfTree->right;
		if (bef) {
			bef->right = pRootOfTree;
		}
		pRootOfTree->left = bef;
		pRootOfTree->right = nullptr;
		bef = pRootOfTree;
		Convert(r);
		return l?l: pRootOfTree;
    }
};