采用中序遍历的思路进行解题

最后需要得到的是一个双相队列，将左指向指向小，右指向指向大

设置递归出口，当节点为空，停止递归

step1：先向左递归

step2：中间操作，有两种情况，一种是没有找到队头，将当前节点作为对头和前节点。第二种情况四有对头的情况，前节点的右指向当前节点，当前节点的左指向前节点，再将当前节点赋值给前节点

step3:向右递归

class Solution {
private:
	TreeNode* head = nullptr,* pre = nullptr;
	void InOrder(TreeNode* root){
		if(root == nullptr){
			return ;
		}
		InOrder(root->left);
		if(pre == nullptr){
			pre = root;
			head = root;
		}else{
			pre->right = root;
			root->left = pre;
			pre = root;
		}
		InOrder(root->right);
	}
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
		if(pRootOfTree==nullptr){
			return nullptr;
		}
		InOrder(pRootOfTree);
		return head;
    }
};