Day 16
剑指offer 35.复杂链表的复制
题目描述
解答
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if(head==null) return null;
Map<Node,Node>map=new HashMap<>();
Node key=head;
while(key!=null){
Node value=new Node(key.val);
map.put(key,value);
key=key.next;
}
key=head;
while(key!=null){
Node newValue=map.get(key);
newValue.random=map.get(key.random);
newValue.next=map.get(key.next);
key=key.next;
}
key=head;
return map.get(key);
}
}
剑指offer 36.二叉搜索树与双向链表
题目描述
思路
由于要求是排序后的,又是二叉搜索树,因此用中序遍历
// 打印中序遍历
void dfs(Node root) {
if(root == null) return;
dfs(root.left); // 左
System.out.println(root.val); // 根
dfs(root.right); // 右
}
解答
class Solution {
// 1. 中序dfs,递归,
Node pre, head;
public Node treeToDoublyList(Node root) {
// 边界值
if(root == null) return null;
//作用:将root为根节点的树中的节点转换成双向链表
dfs(root);
// 题目要求头尾连接
head.left = pre;
pre.right = head;
// 返回头节点
return head;
}
void dfs(Node cur) {
// 递归结束条件
if(cur == null) return;
//将左子树实现作用
dfs(cur.left);
// 如果pre为空,就说明是第一个节点,头结点,然后用head保存头结点,用于之后的返回
if (pre == null) head = cur;
// 如果不为空,那就说明是中间的节点。并且pre保存的是上一个节点,
// 让上一个节点的右指针指向当前节点
else {
pre.right = cur;
// 再让当前节点的左指针指向父节点,也就连成了双向链表
cur.left = pre;
}
// 保存当前节点,用于下层递归创建
pre = cur;
//将右子树实现作用
dfs(cur.right);
}
}