牛客JZ36 二叉搜索树与双向链表 C++

牛客JZ36 二叉搜索树与双向链表 C++

思路🧐：

代码🔎：

class Solution {
public:
	void InOrder(TreeNode* cur, TreeNode*& prev)
	{
		
		if(cur == nullptr)
			return;
		InOrder(cur->left, prev);

		cur->left = prev;
		if(prev) //如果prev不为空，就说明可以链接
			prev->right = cur;
		prev = cur; //置回cur位置

		InOrder(cur->right, prev);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* cur = pRootOfTree, *prev = nullptr;
		InOrder(cur, prev);

		TreeNode* head = pRootOfTree; //找头
		while(head && head->left) //找链表的头，由于是中序，一直向左找一定能找到
		{
			head = head->left;
		}
		return head;
	}
};