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

class Solution {
public:
	TreeNode* pre;

	void bianli(TreeNode* p){
		if(p->left != NULL) bianli(p->left);
		if(pre != p){   //头节点不用操作
			pre->right = p;
			p->left = pre;
			pre = p;
		}
		if(p->right != NULL) bianli(p->right);
		return;
	}

    TreeNode* Convert(TreeNode* pRootOfTree) {
		if(pRootOfTree == NULL) return {};
        pre = pRootOfTree;
		while(pre->left != NULL) pre = pre->left;   //找到返回值的头节点，用于初始化
		TreeNode* res = pre;   //res为头节点，用于返回
		bianli(pRootOfTree);
		return res;
    }
};
//时空复杂度都是On   没有看到空间O1原地操作的