This post is part of the Algorithms Problem Solving series.
This is the Clone Binary Tree problem. The description looks like this:
Given two binary
given a reference to a node
target in the
cloned tree is a copy of the
Return a reference to the same node in
Note that you are not allowed to change any of the two trees or
target node and the answer must be a reference to a node in
Follow up: Solve the problem if repeated values on the tree are allowed.
Input: tree = [7,4,3,null,null,6,19], target = 3 Output: 3 Input: tree = , target = 7 Output: 7 Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4 Output: 4 Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5 Output: 5 Input: tree = [1,2,null,3], target = 2 Output: 2
The idea of my solution was to traverse the tree, starting from the left to the right side of the tree. To trsverse a tree, we use a recursion. The base case of this recursion is when we find the target value in the cloned tree. When we find it, just return the cloned tree node.
As I said earlier, we start from the left side of the tree. If we find
it, the result will be different than
None, so we just
return the node reference. We do the same thing for the right side of
def get_target_copy(original, cloned, target): if cloned.val == target.val: return cloned if cloned.left: result = get_target_copy(original.left, cloned.left, target) if result: return result if cloned.right: result = get_target_copy(original.right, cloned.right, target) if result: return result