LeetCode 面试题36. 二叉搜索树与双向链表
程序员文章站
2022-07-04 18:37:37
我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 面试题36. 二叉搜索树与双向链表 题目 输入一棵二叉搜索树, ......
我的leetcode:
我的leetcode刷题源码[github]:https://github.com/izhoujie/algorithmcii
leetcode 面试题36. 二叉搜索树与双向链表
题目
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
__注意:__本题与主站 426 题相同:
来源:力扣(leetcode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
思路1-中序遍历然后拼接
中序遍历搜索二叉树可得到排序节点,然后把节点顺序拼接为双向链表即可;
算法复杂度:
- 时间复杂度: $ {\color{magenta}{\omicron\left(n\right)}} $
- 空间复杂度: $ {\color{magenta}{\omicron\left(n\right)}} $ 保存节点的list空间
思路2-中序遍历时就地完成链表转换
在中序遍历时就完成到链表的转换,中间节点的指向操作比较绕,需要仔细分析;
未使用额外空间;
算法复杂度:
- 时间复杂度: $ {\color{magenta}{\omicron\left(n\right)}} $
- 空间复杂度: $ {\color{magenta}{\omicron\left(1\right)}} $
算法源码示例
package leetcode; import java.util.arraylist; import java.util.list; /** * @author zhoujie * @date 2020年3月14日 下午6:10:03 * @description: 面试题36. 二叉搜索树与双向链表 * */ public class leetcode_offer_36 { } //definition for a node. class node_offer_36 { public int val; public node_offer_36 left; public node_offer_36 right; public node_offer_36() { } public node_offer_36(int _val) { val = _val; } public node_offer_36(int _val, node_offer_36 _left, node_offer_36 _right) { val = _val; left = _left; right = _right; } }; class solution_offer_36 { /** * @author: zhoujie * @date: 2020年3月14日 下午7:04:20 * @param: @param root * @param: @return * @return: node_offer_36 * @description: 1-先用list对搜索二叉树顺次保存,然后遍历list组装链表; * */ public node_offer_36 treetodoublylist_1(node_offer_36 root) { if (root == null) { return root; } list<node_offer_36> list = new arraylist<node_offer_36>(); aftertree(root, list); for (int i = 1; i < list.size(); i++) { node_offer_36 node1 = list.get(i - 1); node_offer_36 node2 = list.get(i); node1.right = node2; node2.left = node1; } node_offer_36 node1 = list.get(0); node_offer_36 node2 = list.get(list.size() - 1); node1.left = node2; node2.right = node1; return list.get(0); } /** * @author: zhoujie * @date: 2020年5月12日 下午2:49:49 * @param: @param root * @param: @param list * @return: void * @description: 中序遍历搜索二叉树得到排序list; * */ private void aftertree(node_offer_36 root, list<node_offer_36> list) { if (root == null) { return; } aftertree(root.right, list); list.add(0, root); aftertree(root.left, list); } /** * @author: zhoujie * @date: 2020年3月14日 下午7:14:31 * @param: @param root * @param: @return * @return: node_offer_36 * @description: 2-直接在遍历链表时完成前继指针和后继指针的变换;(还没看太明白) * */ node_offer_36 pre, head, tail; public node_offer_36 treetodoublylist_2(node_offer_36 root) { if (root == null) { return root; } transform(root); head.left = tail; tail.right = head; return head; } private void transform(node_offer_36 root) { if (root == null) { return; } transform(root.left); root.left = pre; if (pre == null) { head = root; } else { pre.right = root; } pre = root; tail = root; transform(root.right); } }
推荐阅读
-
Python二叉搜索树与双向链表转换算法示例
-
C++实现LeetCode(109.将有序链表转为二叉搜索树)
-
LeetCode 426. 将二叉搜索树转化为排序的双向链表(BST中序循环遍历)
-
二叉搜索树(二叉排序树)BST与双向列表的转换
-
1601:面试题36. 二叉搜索树与双向链表
-
[LeetCode] 每日一题:109 有序链表转换二叉搜索树
-
LeetCode每日一题 109. 有序链表转换二叉搜索树
-
leetcode【每日一题】109. 有序链表转换二叉搜索树 Java
-
每日一题——LeetCode109 有序链表转换二叉搜索树
-
[leetcode每日一题2020/8/18]109. 有序链表转换二叉搜索树