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

解法1:中序遍历,将节点放到vector中,再改链接关系

class Solution 
{
public:
	vector<TreeNode*> v;
	void InOrder(TreeNode* root) 
	{
		if(root == nullptr)		return;
		InOrder(root->left);
		v.push_back(root);
		InOrder(root->right);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
		if(pRootOfTree==nullptr)	return nullptr;
		InOrder(pRootOfTree);
		int n = v.size();
		for(int i=0;i<n;++i) {
			auto x = v[i];
			if(i==0) {
				x->left=nullptr;
				x->right=v[i+1];
			}
			else if(i==n-1) {
				x->left=v[i-1];
				x->right=nullptr;
			}
			else {
				x->left=v[i-1];
				x->right=v[i+1];
			}
		}
		return v[0];
    }
};

解法2:直接在树上处理

class Solution 
{
public:
	// 只有一个prev,如果不加引用每次递归建立栈帧的时候prev不会改变
	void InOrderConvert(TreeNode* cur, TreeNode*& prev) 
	{
		if(cur==nullptr)	return;
		InOrderConvert(cur->left, prev);
		cur->left=prev;
		if(prev != nullptr)		prev->right=cur;
		prev=cur;
		InOrderConvert(cur->right, prev);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
		// 找到最左节点
		auto head = pRootOfTree;
		while(head && head->left != nullptr)	
			head=head->left;
		TreeNode* prev = nullptr;
		InOrderConvert(pRootOfTree, prev);
		return head;
    }
};