二叉搜索树与双向链表（C++）

文章目录

1. 题目描述
2.题目解析

题目来源：牛客网…二叉搜索树与双向链表

1. 题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

在这里插入图片描述

数据范围：输入二叉树的节点数 0≤n≤1000，二叉树中每个节点的值 0≤val≤1000
要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n)

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出

输入描述：
二叉树的根节点
返回值描述：
双向链表的其中一个头节点。
示例1

输入： {10,6,14,4,8,12,16}
返回值： From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明：输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。

示例2

输入：{5,4,#,3,#,2,#,1} 返回值：From left to right are:1,2,3,4,5;From right
to left are:5,4,3,2,1;

在这里插入图片描述

2.题目解析

将二叉搜索树（BST）转换为双向链表（Doubly Linked List）的思路如下：

利用二叉搜索树的中序遍历特性，中序遍历二叉搜索树可以得到一个有序的节点序列。
在中序遍历的过程中，逐步调整每个节点的左右指针，使其构成一个双向链表。
核心

具体步骤如下：

定义一个指针 prev，用于记录当前节点的前一个节点。
按照中序遍历的顺序，依次处理左子树、当前节点、右子树。
在处理当前节点时，将当前节点的左指针指向 prev 节点（如果 prev 存在），并将 prev 的右指针指向当前节点。然后更新 prev 为当前节点。
遍历结束后，链表构建完成，返回链表头节点指针。

对于当前结点root，有root->left要指向前继prev（中序遍历时，对于当前结点root，其左孩子已经遍历完成了，此时root->left可以被修改。）；同时，prev->right要指向当前结点（当前结点是prev的后继），此时对于prev结点，它已经完全加入双向链表。
画个图理解一下：
在这里插入图片描述
代码如下：

void  _Convert(TreeNode* root, TreeNode*& prev) 
{
	//空树直接返回，无需转换
	if (root == nullptr) return;
	//先将其左子树完成转换
	_Convert(root->left, prev);
	//左子树转换完以后，将当前节点的左指针指向 prev 节点
	root->left = prev;
	//如果 prev 存在，将 prev 的右指针指向当前节点
	if (prev)
		prev->right = root;
	//然后更新 prev 为当前节点
	prev = root; 
	//再去完成左子树的转换
	_Convert(root->right, prev);
}
TreeNode* Convert(TreeNode* root) 
{
	 TreeNode* prev = nullptr;
	_Convert(root, prev);
	//找转换完以后的链表的头指针
	while (root && root->left)
	{
		root = root->left;
	}
	return root;
}