Corresponding Node in a Cloned Tree
Apple● MediumNEW GRADONSITE INTERVIEWProblem statement
Two binary trees have exactly the same structure and corresponding node values. The second tree is a separate clone of the first. Given a target node in the original tree, return the identifier of its corresponding node in the cloned tree. Do not modify either tree.
Each tree is represented by rows [nodeId,value,leftId,rightId], in arbitrary row order. -1 means no child. The root identifiers are originalRoot and clonedRoot, and targetId identifies an existing original node.
For this exercise, node values are unique within each tree. Original and cloned node identifiers are globally disjoint. Return the corresponding cloned identifier; a node value is data and may numerically coincide with an identifier.
Function
correspondingCloneNode(original: int[][], cloned: int[][], originalRoot: int, clonedRoot: int, targetId: int) → intExamples
Example 1
original = [[10,7,20,30],[20,4,-1,-1],[30,3,-1,-1]]cloned = [[100,7,200,300],[200,4,-1,-1],[300,3,-1,-1]]originalRoot = 10clonedRoot = 100targetId = 20return = 200The original left child has identifier twenty; its cloned counterpart has identifier two hundred.
Example 2
original = [[10,7,20,30],[20,4,-1,-1],[30,3,-1,-1]]cloned = [[100,7,200,300],[200,4,-1,-1],[300,3,-1,-1]]originalRoot = 10clonedRoot = 100targetId = 10return = 100The root corresponds to the cloned root, whose identifier differs from the original root.
Constraints
- Both inputs represent valid nonempty binary trees with the same
n, where1 <= n <= 20000. - Node identifiers are distinct integers in
[0,10^9]; child references are valid within their tree or-1. - Node values are unique integers in
[-10^9,10^9], equal at corresponding positions.