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

/*
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) {
		if(pRootOfTree==nullptr){
			return nullptr;
		}
		TreeNode * ret=dfs(pRootOfTree);
		TreeNode * retlast=ret->left;
		retlast->right=nullptr;
		ret->left=nullptr;

		return ret;

    }
	TreeNode * dfs(TreeNode * pRootOfTree){
		if(pRootOfTree==nullptr){
			return nullptr;
		}
	
		TreeNode * left=dfs(pRootOfTree->left);
		TreeNode * right=dfs(pRootOfTree->right);
		TreeNode * start=pRootOfTree;
		TreeNode * end=pRootOfTree;
		
		if(left!=nullptr){
			TreeNode * leftLast=left->left;
			leftLast->right=pRootOfTree;
			pRootOfTree->left=leftLast;
		//	left->left=nullptr;
			start=left;
		}//middle
		//process right sub tree
		//将中间节点拼接到右边子树的开头，把末尾和开头相连。
		if(right!=nullptr){
			TreeNode * rightLast=right->left;
			pRootOfTree->right=right;
			right->left=pRootOfTree;
			end=rightLast;
		}

		start->left=end;
		end->right=start;

		return start;
	}
};

递归，关键是确定好三种条件：

1.主节点nullptr

2.左右子节点nullptr的情况

3.考虑递归到最下层节点的情况

总之，

1.等价于处理左子树，生成链表

2.处理右子树，生成链表

3.中间节点接在左子树末端，再接到右子树首端

4.既然都是返回头结点或者尾节点，怎么才能获取左子树末端的情况？

确认返回的是循环链表。

所以算法是

1.生成循环链表，从小到大，返回头

2.同样

3.中间节点接好

4.返回循环链表

5.最外一层，调用，并且解开。