LeetCode 面试题36. 二叉搜索树与双向链表
2020-05-12 16:04:16来源:博客园 阅读 ()
LeetCode 面试题36. 二叉搜索树与双向链表
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode 面试题36. 二叉搜索树与双向链表
题目
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
__注意:__本题与主站 426 题相同:https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
思路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);
}
}
原文链接:https://www.cnblogs.com/izhoujie/p/12876289.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- JVM常见面试题解析 2020-06-11
- 送你一份年薪百万的抖音Java岗内部面试题 2020-06-09
- 总结一些 Java 相关笔试、面试题,万一用上了呢 (=_=) -- 基 2020-06-08
- 最强Dubbo面试题,附带超级详细答案 2020-06-06
- 2020Java面试题及答案,命中率高达90% 2020-06-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash