二叉搜索树与双向链表链接
解题思路
思路1 : 中序遍历,将节点放进vector中,再改链接关系,这很容易想出并解决,但这样明显不符合题意。
思路2:
这道题目要求将一个二叉搜索树转换成一个排序的双向链表,不创建新的节点,只调整指针。
二叉搜索树的特点是左子树的值都小于根节点,右子树的值都大于根节点,中序遍历可以得到一个升序的序列。
因此,我们可以利用中序遍历的顺序,将每个节点的左指针指向前一个节点,将每个节点的右指针指向后一个节点,从而形成一个双向链表。
我们需要用一个变量prev来记录前一个节点,初始为nullptr。然后我们递归遍历二叉树,每次访问到一个节点时,就修改它和prev的指针,并更新prev为当前节点。
最后,我们从根节点开始往左走,找到最左边的节点,即双向链表的头节点,返回即可。
举个栗子:
假设我们有这样一个二叉搜索树:
10
/ \
6 14
/ \ / \
4 8 12 16
我们先初始化prev为空,然后从根节点开始递归遍历二叉树。
首先我们遍历到4这个节点,它没有左子树,所以我们直接修改它的左指针指向prev(此时为空),然后将prev更新为4。
然后我们回到6这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为4),并将4的右指针指向6。然后将prev更新为6。
然后我们遍历到8这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为6),并将6的右指针指向8。然后将prev更新为8。
然后我们回到10这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为8),并将8的右指针指向10。然后将prev更新为10。
然后我们遍历到12这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为10),并将10的右指针指向12。然后将prev更新为12。
然后我们回到14这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为12),并将12的右指针指向14。然后将prev更新为14。
然后我们遍历到16这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为14),并将14的右指针指向16。然后将prev更新为16。
最后我们回到根节点10,并从它开始往左走,找到最左边的节点4,即双向链表的头节点。返回4即可。
此时二叉搜索树已经转换成了如下的双向链表:
NULL <-> 4 <-> 6 <-> 8 <-> 10 <-> 12 <-> 14 <-> 16 <-> NULL
文章来源:https://www.toymoban.com/news/detail-427362.html
代码—加注释
/*
struct TreeNode {
int val; // 节点的值
struct TreeNode *left; // 左子节点的指针
struct TreeNode *right; // 右子节点的指针
TreeNode(int x) : // 构造函数,初始化节点的值和子节点指针
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void InOrderConvert(TreeNode* cur, TreeNode*& prev) {
if (cur == nullptr) // 如果当前节点为空,直接返回
return;
InOrderConvert(cur->left, prev); // 递归遍历左子树
//这里cur出现的顺序就是中序
cur->left = prev; // 将当前节点的左指针指向前一个节点
if (prev) // 如果前一个节点不为空,将其右指针指向当前节点
prev->right = cur;
prev = cur; // 更新前一个节点为当前节点
InOrderConvert(cur->right, prev); // 递归遍历右子树
}
TreeNode* Convert(TreeNode* pRootOfTree) {
TreeNode* prev = nullptr; // 初始化前一个节点为空
InOrderConvert(pRootOfTree,
prev); // 调用辅助函数,中序遍历二叉树,并修改指针
TreeNode* head = pRootOfTree; // 初始化头节点为根节点
while (head &&
head->left) { // 循环找到最左边的节点,即双向链表的头节点
head = head->left;
}
return head; // 返回头节点
}
};
本节完文章来源地址https://www.toymoban.com/news/detail-427362.html
到了这里,关于【经典题】二叉搜索树与双向链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!