# LEETCODE 1485. Clone Binary Tree With Random Pointer 解题思路分析

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]`.

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

```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节点
}```

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.