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

❓ 剑指 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;}
}

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：$O(n)$，其中 n 为二叉树的节点数，中序遍历需要访问所有节点。
• 空间复杂度：$O(n)$，最差情况下，即树退化为链表时，递归深度达到 n，系统使用 $O(n)$ 栈空间。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！

注： 如有不足，欢迎指正！