【leetcode】剑指 Offer 36. 二叉搜索树与双向链表
题目描述:
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
解题思路:
1、遍历二叉搜索树,需要有序输出有序链表。按照中序遍历的方式遍历二叉树;
2、组装成双链表的方式(right相当于双链表的next,left相当于双链表的pre);主要是两种场景:
1) 当表头为空时,将表头的left和right都赋值为当前插入节点;当前节点的left赋值为header(切记当前节点的right节点不要赋值);
curNode->left = header;
header->right = curNode;
header->left= curNode;
2)表头不为空时,插入新节点到双链表尾部;
tail = header->left;
tail->right = curNode;
header->left = curNode;
curNode->right = header;
C++ 源码如下
class Solution {
public:
void DFSLDR(Node *root) {
if (!root) {
return;
}
DFSLDR(root->left);
if (head.right == NULL) {
head.right = root;
root->left = root;
head.left = root;
} else {
Node *tail = head.left;
root->left = tail;
tail->right = root;
head.left = root;
}
DFSLDR(root->right);
}
Node* treeToDoublyList(Node* root) {
head.right = NULL;
if (!root) {
return NULL;
}
DFSLDR(root);
head.right->left = head.left;
head.left->right = head.right;
return head.right;
}
public:
Node head;
};