The Problem
Given two binary trees
original
andcloned
and given a reference to a nodetarget
in the original tree.The
cloned
tree is a copy of theoriginal
tree.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.
Example:
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.
My Tests
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
My Solution
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)
Analysis
My Commentary
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.
Top comments (0)