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

September 14, 2020

We can find the path from $target$ to the root of the tree in $O(log(n))$ time. And with that path, we can walk to the parallel node in the $cloned$ tree.

What path representation should we use? Our path representation needs to be reversible. We could build a list of left/right turns and then walk the list in reverse order on the $cloned$ tree.

Just kidding… we don't have parent pointers in the $TreeNode$ class.

I guess we need to do an $O(n)$ search. We don't have any insight into the distribution of $target$ nodes or the character of tree completeness, so we might as well do a DFS. Since we have to do a graph search on cloned trees, we can do a parallel DFS and return the $cloned$ node when we find the parallel $original$ node that matches $target$ .

This parallel search works for the problem's follow up: Solve the problem if repeated values on the tree are allowed.

from typing import List
import unittest

from .. import TreeNode

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def _get_target(self, t: TreeNode, v: int) -> TreeNode:
        """Gets the TreeNode with val=v.

        Args:
            t: The root of a TreeNode tree.
            v: The node value we're searching for.

        Returns:
            TreeNode: The TreeNode in <t> with val <v>. <None> if no such node exists.
        """
        look_at = [t]
        while look_at:
            pop = look_at.pop()
            if not pop:
                continue
            if pop.val == v:
                return pop
            look_at.append(pop.left)
            look_at.append(pop.right)

    def test_examples(self):
        o = TreeNode.from_list([7,4,3,None,None,6,19])
        c = TreeNode.from_list([7,4,3,None,None,6,19])
        to = self._get_target(o, 3)
        tc = self._get_target(c, 3)
        self.assertIs(self.s.getTargetCopy(o, c, to), tc)
        o = TreeNode.from_list([7])
        c = TreeNode.from_list([7])
        to = self._get_target(o, 7)
        tc = self._get_target(c, 7)
        self.assertIs(self.s.getTargetCopy(o, c, to), tc)
        o = TreeNode.from_list([8,None,6,None,5,None,4,None,3,None,2,None,1])
        c = TreeNode.from_list([8,None,6,None,5,None,4,None,3,None,2,None,1])
        to = self._get_target(o, 4)
        tc = self._get_target(c, 4)
        self.assertIs(self.s.getTargetCopy(o, c, to), tc)
        o = TreeNode.from_list([1,2,3,4,5,6,7,8,9,10])
        c = TreeNode.from_list([1,2,3,4,5,6,7,8,9,10])
        to = self._get_target(o, 5)
        tc = self._get_target(c, 5)
        self.assertIs(self.s.getTargetCopy(o, c, to), tc)
        o = TreeNode.from_list([1,2,None,3])
        c = TreeNode.from_list([1,2,None,3])
        to = self._get_target(o, 2)
        tc = self._get_target(c, 2)
        self.assertIs(self.s.getTargetCopy(o, c, to), tc)

class Solution:

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

if __name__ == "__main__":
    unittest.main()

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

Just kidding… we don't have parent pointers in the TreeNodeTreeNodeTreeNode class.

Just kidding… we don't have parent pointers in the $TreeNode$ class.