【数据结构与算法面试题】二叉查找树转换成双向链表

felixzhao

发布于 2022-03-04 17:08:17

1690

发布于 2022-03-04 17:08:17

文章被收录于专栏：null的专栏null的专栏

题目来源“数据结构与算法面试题80道”。

问题分析：二叉查找树是一种二叉树的结构，其中，根节点的值大于左子树的值，小于右子树的值。而二叉查找树的中序遍历即为排序的结果。对于根节点，前驱指针指向左子树中最大的节点，同理，后驱指针指向右子树中最小的节点，如下图所示：

树是一种递归的结果，因此，对于左右子树，也需要执行相同的操作。

方法：

BSTreeNode* convert(BSTreeNode *root){
	if (NULL == root ||
		(NULL == root->m_pLeft && NULL == root->m_pRight)){
		return root;
	}

	convert(root->m_pLeft);
	BSTreeNode* p_left = root->m_pLeft;
	while(p_left->m_pRight != NULL){
		p_left = p_left->m_pRight;
	}
	root->m_pLeft = p_left;
	p_left->m_pRight = root;

	convert(root->m_pRight);
	BSTreeNode* p_right = root->m_pRight;
	while(p_right->m_pLeft != NULL){
		p_right = p_right->m_pLeft;
	}
	root->m_pRight = p_right;
	p_right->m_pLeft = root;
	
	BSTreeNode *p = root;
	while (NULL != p->m_pLeft){
		p = p->m_pLeft;
	}
	return p;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树