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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
		TreeNode* prev = nullptr;
        InOrderList(pRootOfTree,prev);//用中序遍历去完成链接操作

		//找到头结点并返回
		TreeNode* head = pRootOfTree;
		while(head && head->left)
			head = head->left;
		return head;
		
    }
	void InOrderList(TreeNode* cur,TreeNode*& prev)//这里的prev要传引用，这样可以保证他们共用的是一个prev
	{
		if(cur == nullptr)//如果是空就跳出
			return;

		InOrderList(cur->left,prev);//先去遍历左子树

		cur->left = prev;//当前左节点给上一个节点
		if(prev)
			prev->right = cur;//上一个的右节点指向当前节点
		prev = cur;//现在当前节点成了上一个，再去右子树递归
		InOrderList(cur->right,prev);
		
	}//思路：因为找不到下一个节点，所以只能让当前节点和上一个节点创建双向关系，那当前节点和下一个节点的关系就要靠下一次递归来完成
};