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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <ios>
#include <utility>
#include <vector>
class Solution {
public:
    TreeNode* Convert(TreeNode* root) {
        if(root == nullptr)
			return nullptr;
		TreeNode* Left = Convert(root->left,root).second;
		TreeNode* Right = Convert(root->right,root).first;
		if(Left!=nullptr){
			root->left = Left;
			Left->right = root;
		}
		if(Right!=nullptr){
			root->right = Right;
			Right->left = root;
		}
		//cout<<root->right->val<<endl;
		while(root->left!=nullptr)
			root = root->left;
		return root;
    }
	pair<TreeNode*,TreeNode*> Convert(TreeNode* root, TreeNode* father){
		pair<TreeNode*,TreeNode*> resultLeft;
		pair<TreeNode*,TreeNode*> resultRight;
		if(root==nullptr)
			return make_pair(nullptr, nullptr);
		TreeNode* MinNode = nullptr;
		TreeNode* MaxNode = nullptr;
		if(root->left!=nullptr){
			resultLeft = Convert(root->left,root);
			MinNode = resultLeft.first;
			root->left = resultLeft.second;
			resultLeft.second->right = root;
		}
		else{
			MinNode = root;
			if(root==father->right)
				root->left = father;
		}
		if(root->right!=nullptr){
			resultRight = Convert(root->right,root);
			MaxNode = resultRight.second;
			root->right = resultRight.first;
			resultRight.first->left = root;
		}
		else{
			MaxNode = root;
			if(root==father->left)
				root->right = father;
		}
		return make_pair(MinNode, MaxNode);
	}
};

基本思路就是完成一个递归函数，功能是同时返回当前结点为根结点的树的最小结点和最大结点，同时将该输入结点的前驱和后继修改为题目要求的。要注意每个方向的递归调用只能执行一次，因为执行之后它的左子树内部结点的前驱和后继都已经修改完了，因此不能执行第二次。需要注意的地方就是当某一边子树为空时，要考虑前驱或者后继可能是父亲结点的情况。比如当前结点是父节点的左子树，且自己没有右子树，则说明父节点是该结点的后继。

其实最核心的点就是，每次遍历一个结点，既需要得到它左子树的最小结点（因为它自己的最小结点就是它左子树的最小结点），又需要它左子树的最大结点（作为自己结点的前驱）。但是它左子树只能遍历一遍，因此函数必须同时返回最大和最小。