関小君刷题记

题目大意：

克隆含随机指针的二叉树

A binary tree is given such that each node contains an additional random pointer which could point to any node in the tree or null.

Return a deep copy of the tree.

The tree is represented in the same input/output way as normal binary trees where each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (in the input) where the random pointer points to, or null if it does not point to any node.

You will be given the tree in class Node and you should return the cloned tree in class NodeCopy. NodeCopy class is just a clone of Node class with the same attributes and constructors.

Example 1:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

Example 2:

Input: root = [[1,4],null,[1,0],null,[1,5],[1,5]]
Output: [[1,4],null,[1,0],null,[1,5],[1,5]]
Explanation: The random pointer of a node can be the node itself.

Example 3:

Input: root = [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]
Output: [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]

Example 4:

Input: root = []
Output: []

Example 5:

Input: root = [[1,null],null,[2,null],null,[1,null]]
Output: [[1,null],null,[2,null],null,[1,null]]

Constraints:

• The number of nodes in the tree is in the range [0, 1000].
• Each node’s value is between [1, 10^6].

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1485

解题思路分析：

我们之前的文章多次提到过二叉树问题多数需要使用dfs深度优先搜索来解题。本题与普通的二叉树相比，节点中多了一个随机节点，这样一来，树形结构实际上就成为了一个可能带有环路的有向图形结构。进而从根节点开始向下进行dfs路径搜索时会导致某些节点重复被访问。在做深度拷贝时，我们需要重新创建（new）一个新的节点对象，而对于重复被访问的节点，我们则不能再次创建新的对象，而是应该使用之前已经被拷贝过的节点对象。因此，我们需要记录下已被访问过的节点列表，本题使用HashMap存储该列表比较方便，其中key为原节点，value为拷贝过的新节点。

dfs递归方法的参数是当前节点，返回值为拷贝后的节点。我们首先判断当前节点是否存在于Map中，如果存在，直接返回。反之创建一个新的节点对象copy。并将当前节点与该copy对象作为key和value存入HashMap。copy的左节点的拷贝对象为dfs递归子问题的返回结果，右节点与随机节点同理递归至子问题即可。递归的终止条件为当前节点为空。

另外本题与 LEETCODE 138. Copy List with Random Pointer 解题思路分析 的描述几乎完全一致，只不过将二叉树换成了链表而已。如果你已经掌握了本题的解法，强烈建议你再去做一下LEETCODE 138来加深印象。

实现代码：

Map<Node, NodeCopy> map=new HashMap<>(); // 存储已经访问/拷贝过的节点
public NodeCopy copyRandomBinaryTree(Node root) {
    return copy(root); // dfs递归深度拷贝
}

NodeCopy copy(Node root){
    if(root==null) return null;
    if(map.containsKey(root)){ // 如果当前节点已被拷贝过
        return map.get(root); // 返回拷贝过的节点对象
    }
    NodeCopy copy=new NodeCopy(root.val); // 新建节点对象
    map.put(root, copy); // 将该对象存入Map
    copy.left=copy(root.left); // dfs递归拷贝左子节点
    copy.right=copy(root.right); // dfs递归拷贝左右节点
    copy.random=copy(root.random); // dfs递归拷贝随机节点
    return copy; // 返回copy节点
}

本题解法执行时间为10ms。

Runtime: 10 ms, faster than 29.40% of Java online submissions for Clone Binary Tree With Random Pointer.

Memory Usage: 40.7 MB, less than 100.00% of Java online submissions for Clone Binary Tree With Random Pointer.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1485-clone-binary-tree-with-random-pointer-解题思路分析/