Given two binary trees
clonedand given a reference to a node
targetin the original tree.
clonedtree is a copy of the
Return a reference to the same node in the cloned tree.
Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.
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 Explanation: In all examples, the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.
import copy from .util import TreeNode from.Day2 import Solution s = Solution() def test_find_node(): tree = TreeNode(7) tree.left = TreeNode(4) tree.right = TreeNode(3) tree.right.left = TreeNode(6) tree.right.right = TreeNode(19) original = tree clone = copy.deepcopy(tree) assert s.getTargetCopy(original, clone, tree.right).val == 3
from .util import TreeNode def search(tree: TreeNode, val: int) -> TreeNode: if tree.val == val: return tree if tree.left is not None: l = search(tree.left, val) if l is not None: return l if tree.right is not None: r = search(tree.right, val) if r is not None: return r return None class Solution: def getTargetCopy( self, original: TreeNode, cloned: TreeNode, target: TreeNode ) -> TreeNode: return search(cloned, target.val)
At first, I thought this one seemed a little bit too easy. I usually find most of the problems hard. Even the "easy" ones. I was a bit confused by the fact that we got the original tree. A search seemed to do the trick. I thought I got a solution pretty quickly and the analysis looked good but then I noticed the memory. I am apparently not doing good with memory usage at all.
I didn't have much time that day so I didn't get to work on a better solution or the follow-up question.
I can only assume we can use the original tree in some way to speed it up or maybe it's just my lack of python knowledge letting me down. I am bookmarking this one to come back to later.