当前位置：首页 > news >正文

(树) 剑指 Offer 36. 二叉搜索树与双向链表 ——【Leetcode每日一题】

news 2025/7/6 19:17:22

❓ 剑指 Offer 36. 二叉搜索树与双向链表

难度：中等

输入一棵二叉搜索树，将该二叉搜索树转换成一个 排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：
在这里插入图片描述
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

在这里插入图片描述
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

注意：此题对比原题有改动。

💡思路：中序递归遍历

由二叉搜索树的性质：中序遍历即为 递增序列。所以可以在中序遍历的时候完成双向链表的转化：

定义两个结点 head 和 end 分别指向已转换链表的 头结点 和 尾结点；

inOrder(root) ：中序递归遍历：

终止条件：当 root 为空时，返回；
递归调用左子树：inOrder(root.left) ;
构建链表：
- 当到达树的最左边的第一个叶子节点，即为 head；
- 当 end 不为空时，修改双向结点引用，即 end.right = root, root.left = end；
- 更新 end ，即 end = root;
递归调用右子树， inOrder(root.right) 。

最后将双向链表首尾相连：head.left = end , end.right = head。

🍁代码：(C++、Java)

C++

/*
// 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 {
private:Node* head = nullptr;Node* end = nullptr;void inOrder(Node* root){if(root == nullptr) return;inOrder(root->left);if(head == nullptr) head = root;//树的最左边的第一个叶子节点为headroot->left = end;if(end != nullptr) end->right = root;end = root;inOrder(root->right);}
public:Node* treeToDoublyList(Node* root) {inOrder(root);if(head != nullptr){head->left = end;end->right = head;}return head;}
};

Java

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node() {}public Node(int _val) {val = _val;}public Node(int _val,Node _left,Node _right) {val = _val;left = _left;right = _right;}
};
*/
class Solution {private Node head = null;private Node end = null;private void inOrder(Node root){if(root == null) return;inOrder(root.left);if(head == null) head = root;//树的最左边的第一个叶子节点为headroot.left = end;if(end != null) end.right = root;end = root;inOrder(root.right);}public Node treeToDoublyList(Node root) {inOrder(root);if(head != null){head.left = end;end.right = head;}return head;}
}