This is the 9th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Thank you very much for reading this article ~ welcome 【👍 like 】【⭐ collect 】【📝 comment 】~ Give up is easy, but insist must be cool ~ HOPE we can all make a little progress every day ~ Original ~ https://juejin.cn/user/2771185768884824/posts blog

1379. Find the same node in the clone binary tree:

You are given two binary trees, the primal tree Original and the clone tree, and a target node, target, located in the primal tree Original.

Wherein, clone tree verification is a copy of the original tree.

Find a node identical to target in the tree verification, and return a reference to that node (a node pointer is returned in languages with Pointers, such as C/C++, and the node itself is returned in other languages).

Note:

  1. youCan’tFor two binomial trees, andtargetThe node changes.
  2. onlyReturns the clone treeclonedA reference to an existing node in.

Advanced: If the tree allows the same value of nodes, how would you answer?

Sample 1:

Input: tree = [7,4,3,null,null,6,19], target = 3 The target node is in the tree Original, marked in green. The answer is yellow-coloured nodes in the tree verification (the other examples are similar).Copy the code

Example 2:

Input: tree = [7], target = 7 Output: 7Copy the code

Sample 3:

Input: tree = [5, 6, 8, null, null, null, 4, null, 3, null, 2, null, 1], the output target = 4:4Copy the code

Example 4:

Input: tree =,2,3,4,5,6,7,8,9,10 [1], target = 5 output: 5Copy the code

The sample 5:

Input: tree = [1,2,null,3] target = 2 output: 2Copy the code

Tip:

  • The number of nodes in the tree ranges from [1, 104].
  • There are no nodes of the same value in the same tree.
  • targetNode is treeoriginalA node in, and will not benull 。

Analysis of the

  • Three parameters: the first parameteroriginalIs the original tree; Second parameterclonedIs a clone of the first argument; The third parametertargetIs the node we want to find, and that’s the first parameteroriginalTo find and return the second argumentclonedThe corresponding node in.
  • It says there are no nodes of the same value in the same tree. So some partners may feel that the first parameter is very redundant, the two masters also feel so. Let’s go straight through the second argumentcloned, until and the third argument is foundtargetReturn a node with the same value.
  • In fact, the first parameter is useful for advanced challenges, if the tree allows nodes with the same value, then the value cannot be used to determine the same node.
  • That’s where the first argument comes inoriginalBecause of the third parametertargetIs a node in the original tree, so we can directly determine whether it is the same node based on the address.
  • Second parameterclonedIs a clone copy of the first parameter, so they have the same structure, and we can find the answer by walking both the original tree and the clone tree in the same order.

Answer key

java

Non-recursive traversal

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        Deque<TreeNode> stack      = new LinkedList<>();
        TreeNode        node       = original;
        TreeNode        clonedNode = cloned;
        while(node ! =null| |! stack.isEmpty()) {if(node ! =null) {
                if (node == target) {
                    return clonedNode;
                }
                stack.push(clonedNode);
                stack.push(node);
                node = node.left;
                clonedNode = clonedNode.left;
            } else{ node = stack.pop().right; clonedNode = stack.pop().right; }}return null; }}Copy the code

The recursive traversal

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if (cloned == null
                || original == target) {
            return cloned;
        }
        TreeNode ans = getTargetCopy(original.left, cloned.left, target);
        if (ans == null) {
            ans = getTargetCopy(original.right, cloned.right, target);
        }
        returnans; }}Copy the code

c++

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; * /

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if (cloned == nullptr
            || original == target) {
            return cloned;
        }
        TreeNode* ans = getTargetCopy(original->left, cloned->left, target);
        if (ans == nullptr) {
            ans = getTargetCopy(original->right, cloned->right, target);
        }
        returnans; }};Copy the code

python

# Definition for a binary tree node.
# 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 cloned is None or original == target:
            return cloned
        ans = self.getTargetCopy(original.left, cloned.left, target)
        if ans is None:
            ans = self.getTargetCopy(original.right, cloned.right, target)
        return ans
        
Copy the code

Portal: https://leetcode-cn.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/