题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路：
递归回溯维护当前子树的最小值节点、最大值节点组成的pair。如果是左子树，那么应该取最大值节点来与当前节点关联；如果是右子树，取最小值与当前节点关联。同时记录链表的头结点，由于是二叉搜索树，所以只需要找到最小值的节点即可。
class Solution {
public:
//记录所有节点中值最小的节点为链表头结点
TreeNode *newHead = NULL;
pair<TreeNode*, TreeNode*> myConvert(TreeNode* root){
if(root == NULL){
return make_pair(root, root);
}
if(newHead == NULL){
newHead = root;
}else{
//找最小的节点
newHead = newHead->val > root->val? root: newHead;
}
if(root->left == NULL && root->right == NULL){
return make_pair(root, root);
}
//维护子树中的最小值、最大值节点
pair<TreeNode*, TreeNode*> lret;
pair<TreeNode*, TreeNode*> rret;
if(root->left != NULL){
lret = myConvert(root->left);
//左子树中最大值节点与当前节点关联
TreeNode* scd = lret.second;
root->left = scd;
scd->right = root;
}
if(root->right != NULL){
rret = myConvert(root->right);
//右子树中最小值节点与当前节点关联
TreeNode* fst = rret.first;
root->right = fst;
fst->left = root;
}
//返回当前子树中最小值节点和最大值节点
TreeNode* lt = root;
TreeNode* rt = root;
if(lret.first != NULL){
lt = lret.first;
}
if(rret.second != NULL){
rt = rret.second;
}
return make_pair(lt, rt);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == NULL){
return NULL;
}
newHead = pRootOfTree;
pair<TreeNode*, TreeNode*>lret;
if(pRootOfTree->left != NULL){
lret = myConvert(pRootOfTree->left);
TreeNode* scd = lret.second;
pRootOfTree->left = scd;
scd->right = pRootOfTree;
}
pair<TreeNode*, TreeNode*> rret;
if(pRootOfTree->right != NULL){
rret = myConvert(pRootOfTree->right);
TreeNode* fst = rret.first;
pRootOfTree->right = fst;
fst->left = pRootOfTree;
}
return newHead;
}
};