广州建设银行保安招聘网站,seo网站排名软件,企业信用信息公示系统年报怎么填,wordpress短链接提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣1485. 克隆含随机指针的二叉树二、力扣1490. 克隆 N 叉树三、力扣133. 克隆图四、力扣138. 随机链表的复制 前言 复制带有随机指针的二叉树或者链表文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣1485. 克隆含随机指针的二叉树二、力扣1490. 克隆 N 叉树三、力扣133. 克隆图四、力扣138. 随机链表的复制 前言 复制带有随机指针的二叉树或者链表或者图先设置一个map作为映射原节点与复制后节点的映射然后正常的遍历返回节点但需要注意的是遍历顺序先遍历其他节点最后遍历随机节点因为随机节点可能没有被创建遍历其他节点时创建复制节点遍历随机节点时查找映射关系返回
一、力扣1485. 克隆含随机指针的二叉树
/*** Definition for Node.* public class Node {* int val;* Node left;* Node right;* Node random;* Node() {}* Node(int val) { this.val val; }* Node(int val, Node left, Node right, Node random) {* this.val val;* this.left left;* this.right right;* this.random random;* }* }*/class Solution {HashMapNode,NodeCopy map new HashMap();public NodeCopy copyRandomBinaryTree(Node root) {if(root null){return null;}if(map.containsKey(root)){return map.get(root);}NodeCopy cur new NodeCopy(root.val);map.put(root,cur);cur.left copyRandomBinaryTree(root.left);cur.right copyRandomBinaryTree(root.right);cur.random copyRandomBinaryTree(root.random);return cur;}
}二、力扣1490. 克隆 N 叉树
/*
// Definition for a Node.
class Node {public int val;public ListNode children;public Node() {children new ArrayListNode();}public Node(int _val) {val _val;children new ArrayListNode();}public Node(int _val,ArrayListNode _children) {val _val;children _children;}
};
*/class Solution {public Node cloneTree(Node root) {if(root null){return null;}Node cur new Node(root.val);cur.children new LinkedListNode();for(Node n : root.children){Node c cloneTree(n);cur.children.add(c);}return cur;}
}三、力扣133. 克隆图
/*
// Definition for a Node.
class Node {public int val;public ListNode neighbors;public Node() {val 0;neighbors new ArrayListNode();}public Node(int _val) {val _val;neighbors new ArrayListNode();}public Node(int _val, ArrayListNode _neighbors) {val _val;neighbors _neighbors;}
}
*/class Solution {HashSetNode visited new HashSet();MapNode,Node originToClone new HashMap();public Node cloneGraph(Node node) {traverse(node);return originToClone.get(node);}void traverse(Node node){if(node null){return;}if(visited.contains(node)){return;}visited.add(node);originToClone.put(node,new Node(node.val));Node copyNode originToClone.get(node);for(Node n : node.neighbors){traverse(n);copyNode.neighbors.add(originToClone.get(n));}}
}四、力扣138. 随机链表的复制
/*
// 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 {MapNode , Node map new HashMap();public Node copyRandomList(Node head) {if(head null){return null;}if(map.containsKey(head)){return map.get(head);}Node cur new Node(head.val);map.put(head,cur);cur.next copyRandomList(head.next);cur.random copyRandomList(head.random);return cur;}
}
