Deep copy
Deep copy is a process in which the copying process occurs recursively. We need to clone all the elements of a tree.
Solution
The overall algorithm is recursive, but we need to find the previous cloned elements. So use a hashmap will help us to store the pair relationship of the elements of source tree and the new cloned elements.
class Solution { public: map<Node*, NodeCopy*> node_map; NodeCopy* copyRandomBinaryTree(Node* root) { if(root == NULL) return NULL; return dfs(root); } NodeCopy* dfs(Node* cur) { if(cur == NULL) return NULL; if(node_map.count(cur)) return node_map[cur]; NodeCopy* node = new NodeCopy(cur->val); node_map[cur] = node; node->left = dfs(cur->left); node->right = dfs(cur->right); node->random = dfs(cur->random); return node; } }; The post LeetCode: Clone Binary Tree With Random Pointer appeared first on Coder's Cat.
Top comments (0)