二叉搜索树与双向链表_牛客题霸_牛客网

方法一：

	void dfs(TreeNode* pRootOfTree, TreeNode* &pre)
	{
		if(pRootOfTree == NULL)
			return;
		dfs(pRootOfTree->left, pre);//所有左子树
		if(pre)
			pre->right = pRootOfTree;

		pRootOfTree->left = pre;
		pre = pRootOfTree;//更新pre到下一个结点
		dfs(pRootOfTree->right, pre);//所有结点的右子树
	}
	
	
    TreeNode* Convert(TreeNode* pRootOfTree) {
      if(pRootOfTree == NULL) return pRootOfTree;
	  TreeNode* pre = NULL;
		dfs(pRootOfTree, pre);
	  TreeNode* head = pRootOfTree;
	  //找链表头结点
		while(head->left)
		{
			head = head->left;
		}
		return head;
    }
	
	

方法二：

TreeNode* pre = NULL,*head = NULL;
	void dfs(TreeNode* pRootOfTree)
	{
		if(pRootOfTree == NULL) return;
		dfs(pRootOfTree->left);//所有左子树
		if(pre) pre->right = pRootOfTree;
		else head = pRootOfTree;
		pRootOfTree->left = pre;
		pre = pRootOfTree;//更新pre到下一个结点
		dfs(pRootOfTree->right);//所有结点的右子树
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
      if(pRootOfTree == NULL) return pRootOfTree;
		dfs(pRootOfTree);
		head->left = pre;//最后一个结点
		pre->right = head;//最前一个结点
		return head;
    }