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

/*
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 *cur = pRootOfTree,*prev = nullptr;
		InOrderList(cur, prev);//因为二叉搜索树的中序遍历就是有序，所以用中序遍历递归的顺序去链接
		//链接完后，找到该链表的头，并返回
		while(cur && cur->left)
		{
			cur = cur->left;
		}	
		return cur;
	}
	void InOrderList(TreeNode* cur,TreeNode*& prev)//prev必须传引用，这样才能保证当前栈帧中改变的prev能应用到其他栈帧中
	{
		if(cur == nullptr)//如果是空，就跳出
			return;

		InOrderList(cur->left,prev);//先遍历左子树
		//此时左子树的根节点就通过34行赋给prev了，如果prev不是引用，下面的操作就不对了
		cur->left = prev;//将当前节点的左指向上一个节点
		if(prev)
			prev->right = cur;//将上一个节点的右指向当前节点
		//此时就将当前节点和上一个节点的链接完成了，因为找不到下一个节点，所以当前节点和下一个节点的链接只能在下次递归时完成
		prev = cur;//将当前节点变成上一个节点，这样在下面递归时才能将上当前节点和下一个节点链接
		InOrderList(cur->right,prev);
	}
};