{"id":6468,"date":"2020-03-13T22:58:43","date_gmt":"2020-03-14T05:58:43","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6468"},"modified":"2020-03-13T22:59:52","modified_gmt":"2020-03-14T05:59:52","slug":"leetcode-1379-find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1379-find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree"},"content":{"rendered":"\n

Given two binary trees original<\/code> and cloned<\/code> and given a reference to a node target<\/code> in the original tree.<\/p>\n\n\n\n

The cloned<\/code> tree is a copy of<\/strong> the original<\/code> tree.<\/p>\n\n\n\n

Return a reference to the same node<\/em> in the cloned<\/code> tree.<\/p>\n\n\n\n

Note<\/strong> that you are not allowed<\/strong> to change any of the two trees or the target<\/code> node and the answer must be<\/strong> a reference to a node in the cloned<\/code> tree.<\/p>\n\n\n\n

Follow up:<\/strong> Solve the problem if repeated values on the tree are allowed.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> tree = [7,4,3,null,null,6,19], target = 3\nOutput:<\/strong> 3\nExplanation:<\/strong> 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.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> tree = [7], target =  7\nOutput:<\/strong> 7\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4\nOutput:<\/strong> 4\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> tree = [1,2,3,4,5,6,7,8,9,10], target = 5\nOutput:<\/strong> 5\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> tree = [1,2,null,3], target = 2\nOutput:<\/strong> 2\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • The number of nodes in the tree<\/code> is in the range [1, 10^4]<\/code>.<\/li>
  • The values of the nodes of the tree<\/code> are unique.<\/li>
  • target<\/code> node is a node from the original<\/code> tree and is not null<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: Recursion<\/strong><\/h2>\n\n\n\n
    Traverse both trees in the same order, if original == target, return cloned.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(h)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\nclass Solution {\npublic:\n  TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {\n    if (!original) return nullptr;\n    if (original == target) return cloned;\n    auto l = getTargetCopy(original->left, cloned->left, target);\n    auto r = getTargetCopy(original->right, cloned->right, target);\n    return l ? l : r;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    \n
    Python3<\/h2>\n
    \n\n
    # Author: Huahua\nclass Solution:\n  def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n    if not original: return None\n    if original == target: return cloned\n    return self.getTargetCopy(original.left, cloned.left, target) or \\\n           self.getTargetCopy(original.right, cloned.right, target)\n<\/pre>\n<\/div><\/div>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[177,17,28],"class_list":["post-6468","post","type-post","status-publish","format-standard","hentry","category-tree","tag-medium","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6468","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6468"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6468\/revisions"}],"predecessor-version":[{"id":6470,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6468\/revisions\/6470"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6468"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6468"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6468"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}