克隆含随机指针的二叉树

/*
 * 思路：
 * 1. 使用深度优先搜索(DFS)的方法来遍历原树。
 * 2. 使用一个HashMap来存储原节点和对应的新节点之间的映射关系，以便处理随机指针。
 * 3. 首先复制树的节点结构，然后根据映射关系复制随机指针。
 * 由于Java Stream主要用于处理集合，不能直接应用于树结构的深度拷贝，此处依然采用常规递归方式。
 */
import java.util.HashMap;

class Node {
    int val;
    Node left;
    Node right;
    Node random;
    Node(int x) { val = x; }
}

public class SolutionStream {
    public Node copyRandomBinaryTree(Node root) {
        if (root == null) return null;
        HashMap<Node, Node> map = new HashMap<>();
        return cloneNodes(root, map);
    }

    private Node cloneNodes(Node root, HashMap<Node, Node> map) {
        if (root == null) return null;
        if (map.containsKey(root)) return map.get(root);

        Node newNode = new Node(root.val);
        map.put(root, newNode);
        newNode.left = cloneNodes(root.left, map);
        newNode.right = cloneNodes(root.right, map);
        newNode.random = map.get(root.random);  // 处理随机指针
        return newNode;
    }
}