---

目录

题目描述

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

题目解析

题目答案

最后

---

题目描述

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

---

题目解析

这里采用的是采用前序遍历的思想，找到要转换的双向链表的头节点也就是这个二叉搜索树的最左节点，找到之后依次递归，采用两个指针的模式，cur和prev，令cur->left=prev prev->right=cur,改变其指针指向，转化成双向链表。然后再去取二叉搜索树的根节点head，一直使其head=head->left，就可以找到双向链表的头节点。

---

题目答案

class Solution {
public:

	void Inoder(TreeNode* cur, TreeNode*& prev)
	{
		if (cur == nullptr)
		{
			return;
		}

		Inoder(cur->left, prev);

		cur->left = prev;
		if (prev != nullptr)
		{
			prev->right = cur;

		}
		prev = cur;
		Inoder(cur->right, prev);
	}

	TreeNode* Convert(TreeNode* pRootOfTree) {

		TreeNode* prev = nullptr;
		Inoder(pRootOfTree, prev);

		TreeNode* head = pRootOfTree;

		while (head && head->left)
		{
			head = head->left;
		}
		return head;
	}
};

---

最后

加油