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

关键点1：二叉搜索树的中序遍历有序

关键点2：为了进行节点的链接，应引入前一个节点的引用 prev

在中序遍历的过程中对两两节点进行链接

class Solution {
public:
    void InOrder(TreeNode* cur, TreeNode*& prev)
    {
        if(cur == nullptr) {
            return;
        }

        InOrder(cur->left, prev);
        //当前节点的前驱指针应指向前一个遍历的节点
        cur->left = prev;
        //前一个被遍历的节点的后继指针应指向当前节点
        if(prev) {
            prev->right = cur;
        }
        prev = cur;
        InOrder(cur->right, prev);
    }

    TreeNode* Convert(TreeNode* pRootOfTree)
	{
		TreeNode* prev = nullptr;
		InOrder(pRootOfTree, prev);
		TreeNode* head = pRootOfTree;
	  	//找链表头节点以返回
		while(head && head->left) {
			head = head->left;
		}
		return head;
    }
};