二叉搜索树与双向链表
注:该题解是lc上可以ac的,在acwing上是TLE的。不过简洁的代码可以给需要的同学参考。
题意:输入一个二叉搜索树,建立一个有序的双向链表,返回最左边元素(最小或者最大)的结点指针。样例都是从小到大有序。
思路:按照二叉树的中序遍历dfs来做。有序这个要求正好由二叉搜索树的中序序列提供。
双向这个要求需要用一个指针pre来做。cur是当前遍历的节点,pre是cur的中序序列前驱节点。
在dfs实现中序遍历时,
- 当cur的前驱pre为空指针时,说明cur就是中序序列的最开始的节点,即head。
- 当cur的前驱pre不是空指针时,就让
pre->right
等于cur。起的作用是建立双向链表的右方向。 - 当然,dfs中无时无刻不需要将
cur->left
置为pre,起的作用是建立双向链表的左方向。 - 另外,我们需要让链表节点不停得往前走,这就要
pre = cur
来实现。
在dfs中序遍历结束的时,
pre指针指向的是中序序列最后一个节点。所以,在dfs结束之后,最后一步是手动链接head(第一个节点)和pre(最后一个节点),构成循环链表。
时间复杂度:$O(n)$
空间复杂度:$O(n)$
ac代码:
对应的是leetcode,剑指offer 36题 剑指 Offer 36. 二叉搜索树与双向链表
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public:
// head是最后的头节点,pre记录当前节点cur的中序前驱
Node *head, *pre;
// 中序遍历dfs,cur为当前节点
void dfs(Node* cur) {
if (cur == nullptr) return;
dfs(cur->left); // 左子树
// 当前节点
// 头节点head,pre是它的前驱,当pre为null时,说明head为第一个节点,即头节点
if (pre == nullptr) head = cur;
else pre->right = cur;
cur->left = pre;
pre = cur;
dfs(cur->right); // 右子树
} // dfs结束时,pre指向双向链表的尾节点(数最大的值)
Node* treeToDoublyList(Node* root) {
if (root == nullptr) return nullptr;
dfs(root);
// 手动链接成循环双链表:收尾相连
pre->right = head;
head->left = pre;
return head; // 返回最小元素的指针
}
};