1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Problem Statement

link: LeetCode.cn LeetCode

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original 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.

Example:

Input: tree = [7,4,3,null,null,6,19], target = 3 Output: 3

Input: tree = [7], target = 7 Output: 7

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4 Output: 4

Constraints:

The number of nodes in the tree is in the range [1, 104]. The values of the nodes of the tree are unique. target node is a node from the original tree and is not null.

Follow up: Could you solve the problem if repeated values on the tree are allowed?

Solution Approach

The solution recursively traverses both trees in parallel, returning the corresponding node from the cloned tree when the target node from the original tree is found.

Algorithm

1. Recursive Traversal: The algorithm uses a recursive approach to simultaneously traverse both the original and cloned trees.
2. Base Case Check: It checks if the current node in the original tree matches the target node, returning the corresponding node from the cloned tree if they match.
3. Depth-First Search (DFS): The method performs a depth-first search to explore both left and right subtrees until the target node is found, ensuring that it handles the entire tree structure efficiently.

Complexity

time complexity: O(n) space complexity: O(h)

Implement

    
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        if target == original:
            return cloned
        if not original or not cloned:
            return None
        l = self.getTargetCopy(original.left, cloned.left, target)
        r = self.getTargetCopy(original.right, cloned.right, target)
        return l if l else r
  

    
    

Twitter  facebook  Email