1485. Clone Binary Tree With Random Pointer

1485. Clone Binary Tree With Random Pointer

概念和 138. Copy List with Random Pointer 一模一樣。

# Definition for Node.
# class Node:
#     def __init__(self, val=0, left=None, right=None, random=None):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.random = random

class Solution:
    def copyRandomBinaryTree(self, root: 'Node') -> 'NodeCopy':
        if not root:
            return None
        table = {}
        copy = NodeCopy(root.val)
        table[root] = copy

        queue = deque([(root, copy)])
        while queue:
            node, copy_node = queue.popleft()
            if node.left:
                copy_node.left = NodeCopy(node.left.val)
                table[node.left] = copy_node.left
                queue.append((node.left, copy_node.left))
            if node.right:
                copy_node.right = NodeCopy(node.right.val)
                table[node.right] = copy_node.right
                queue.append((node.right, copy_node.right))

        queue = deque([root])

        while queue:
            node = queue.popleft()
            if node.random:
                random = table[node.random]
                table[node].random = random
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return table[root]