← Static tasks

1485. Clone Binary Tree With Random Pointer

leetcode medium

#array#csharp#hash-table#leetcode#medium#recursion#tree#two-pointers

Task

Дано бинарное дерево, такое что каждый узел содержит дополнительный случайный указатель, который может указывать на любой узел в дереве или быть null.

Верните глубокую копию дерева.

Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где:

- val: целое число, представляющее Node.val

- random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.

Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.

Пример:

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.

C# solution

matched/original
public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node random;
    public Node(int _val) {
        val = _val;
        left = null;
        right = null;
        random = null;
    }
}
public class NodeCopy {
    public int val;
    public NodeCopy left;
    public NodeCopy right;
    public NodeCopy random;
    public NodeCopy(int _val) {
        val = _val;
        left = null;
        right = null;
        random = null;
    }
}
public class Solution {
    private Dictionary<Node, NodeCopy> newOldPairs = new Dictionary<Node, NodeCopy>();
    private NodeCopy DeepCopy(Node root) {
        if (root == null) return null;
        NodeCopy newRoot = new NodeCopy(root.val);
        newRoot.left = DeepCopy(root.left);
        newRoot.right = DeepCopy(root.right);
        newOldPairs[root] = newRoot;
        return newRoot;
    }
    private void MapRandomPointers(Node oldNode) {
        if (oldNode == null) return;
        if (newOldPairs.TryGetValue(oldNode, out NodeCopy newNode)) {
            newNode.random = newOldPairs.GetValueOrDefault(oldNode.random);
            MapRandomPointers(oldNode.left);
            MapRandomPointers(oldNode.right);
        }
    }
    public NodeCopy CopyRandomBinaryTree(Node root) {
        NodeCopy newRoot = DeepCopy(root);
        MapRandomPointers(root);
        return newRoot;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node random;
    public Node(int _val) {
        val = _val;
        left = null;
        right = null;
        random = null;
    }
}
public class NodeCopy {
    public int val;
    public NodeCopy left;
    public NodeCopy right;
    public NodeCopy random;
    public NodeCopy(int _val) {
        val = _val;
        left = null;
        right = null;
        random = null;
    }
}
class Solution {
public:
    private unordered_map<Node, NodeCopy> newOldPairs = new unordered_map<Node, NodeCopy>();
    private NodeCopy DeepCopy(Node root) {
        if (root == null) return null;
        NodeCopy newRoot = new NodeCopy(root.val);
        newRoot.left = DeepCopy(root.left);
        newRoot.right = DeepCopy(root.right);
        newOldPairs[root] = newRoot;
        return newRoot;
    }
    private void MapRandomPointers(Node oldNode) {
        if (oldNode == null) return;
        if (newOldPairs.TryGetValue(oldNode, out NodeCopy newNode)) {
            newNode.random = newOldPairs.GetValueOrDefault(oldNode.random);
            MapRandomPointers(oldNode.left);
            MapRandomPointers(oldNode.right);
        }
    }
    public NodeCopy CopyRandomBinaryTree(Node root) {
        NodeCopy newRoot = DeepCopy(root);
        MapRandomPointers(root);
        return newRoot;
    }
}

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node random;
    public Node(int _val) {
        val = _val;
        left = null;
        right = null;
        random = null;
    }
}
public class NodeCopy {
    public int val;
    public NodeCopy left;
    public NodeCopy right;
    public NodeCopy random;
    public NodeCopy(int _val) {
        val = _val;
        left = null;
        right = null;
        random = null;
    }
}
public class Solution {
    private HashMap<Node, NodeCopy> newOldPairs = new HashMap<Node, NodeCopy>();
    private NodeCopy DeepCopy(Node root) {
        if (root == null) return null;
        NodeCopy newRoot = new NodeCopy(root.val);
        newRoot.left = DeepCopy(root.left);
        newRoot.right = DeepCopy(root.right);
        newOldPairs[root] = newRoot;
        return newRoot;
    }
    private void MapRandomPointers(Node oldNode) {
        if (oldNode == null) return;
        if (newOldPairs.TryGetValue(oldNode, out NodeCopy newNode)) {
            newNode.random = newOldPairs.GetValueOrDefault(oldNode.random);
            MapRandomPointers(oldNode.left);
            MapRandomPointers(oldNode.right);
        }
    }
    public NodeCopy CopyRandomBinaryTree(Node root) {
        NodeCopy newRoot = DeepCopy(root);
        MapRandomPointers(root);
        return newRoot;
    }
}

JavaScript solution

matched/original
function Node(val, left, right, random) {
    this.val = val;
    this.left = left;
    this.right = right;
    this.random = random;
}

function NodeCopy(val, left, right, random) {
    this.val = val;
    this.left = left;
    this.right = right;
    this.random = random;
}

var copyRandomBinaryTree = function(root) {
    let newOldPairs = new Map();

    function deepCopy(node) {
        if (!node) return null;
        let newNode = new NodeCopy(node.val);
        newNode.left = deepCopy(node.left);
        newNode.right = deepCopy(node.right);
        newOldPairs.set(node, newNode);
        return newNode;
    }

    function mapRandomPointers(node) {
        if (!node) return;
        let newNode = newOldPairs.get(node);
        if (newNode) {
            newNode.random = newOldPairs.get(node.random);
            mapRandomPointers(node.left);
            mapRandomPointers(node.right);
        }
    }

    let newRoot = deepCopy(root);
    mapRandomPointers(root);
    return newRoot;
};

Go solution

matched/original
type Node struct {
    Val int
    Left *Node
    Right *Node
    Random *Node
}

type NodeCopy struct {
    Val int
    Left *NodeCopy
    Right *NodeCopy
    Random *NodeCopy
}

func deepCopy(root *Node, newOldPairs map[*Node]*NodeCopy) *NodeCopy {
    if root == nil {
        return nil
    }
    newRoot := &NodeCopy{Val: root.Val}
    newRoot.Left = deepCopy(root.Left, newOldPairs)
    newRoot.Right = deepCopy(root.Right, newOldPairs)
    newOldPairs[root] = newRoot
    return newRoot
}

func mapRandomPointers(oldNode *Node, newOldPairs map[*Node]*NodeCopy) {
    if oldNode == nil {
        return
    }
    if newNode, found := newOldPairs[oldNode]; found {
        newNode.Random = newOldPairs[oldNode.Random]
        mapRandomPointers(oldNode.Left, newOldPairs)
        mapRandomPointers(oldNode.Right, newOldPairs)
    }
}

func copyRandomBinaryTree(root *Node) *NodeCopy {
    newOldPairs := make(map[*Node]*NodeCopy)
    newRoot := deepCopy(root, newOldPairs)
    mapRandomPointers(root, newOldPairs)
    return newRoot
}

Explanation

Algorithm

Глубокое копирование дерева:

Инициализируйте хэш-таблицу newOldPairs, которая сопоставляет узлы старого дерева с узлами нового дерева.

Создайте функцию deepCopy(root), которая принимает корень данного дерева и возвращает корень нового дерева. Эта функция создаёт новый узел с теми же значениями, что и корневой узел, и рекурсивно копирует левое и правое поддеревья. Затем она сохраняет пару старого и нового узлов в хэш-таблицу и возвращает новый корень.

Сопоставление случайных указателей:

Создайте функцию mapRandomPointers(oldNode), которая принимает корень старого дерева и рекурсивно сопоставляет случайные указатели нового дерева с соответствующими узлами старого дерева, используя хэш-таблицу newOldPairs.

Возвращение клонированного дерева:

Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень.

😎