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

你的名字 2022-10-06 10:49 4阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Breadth-first Search
 *  Recursion

## Description ##

[https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/][https_leetcode.com_problems_find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree]

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.

**Follow up:** Solve the problem if repeated values on the tree are allowed.

**Example 1:**

![4f3f0ce0eae18411919b5680fe461adb.png][]

Input: tree = [7,4,3,null,null,6,19], target = 3
    Output: 3
    Explanation: 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.

**Example 2:**

![a0ad04ad2a7826e8d1ad8cec7a3e1492.png][]

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

**Example 3:**

![f8776dbe2eb2cdf2c39c03b93462e3a0.png][]

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

**Example 4:**  
![9e904078cc60aea9f95fda44ef215018.png][]

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

**Example 5:**

![df30e5dd767aebd29943ad1e862902cb.png][]

Input: tree = [1,2,null,3], target = 2
    Output: 2

**Constraints:**

*  The number of nodes in the `tree` is in the range  \[ 1 , 1 0 4 \] \[1, 10^4\] \[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`.

## Analysis ##

BFS，DFS都行，这题应为Easy难度。

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class FindACorrespondingNodeOfABinaryTreeInACloneOfThatTree { 
       public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) { 
           
    	   LinkedList<TreeNode> stack = new LinkedList<>();
    	   stack.push(cloned);
    	   while(!stack.isEmpty()) { 
    		   TreeNode node = stack.pop();
    		   
    		   if(node.val == target.val)
    			   return node;
    		   
    		   if(node.left != null)
    			   stack.push(node.left);
    		   
    		   if(node.right != null)
    			   stack.push(node.right);
    		   
    	   }
    	   return null;
       }
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class FindACorrespondingNodeOfABinaryTreeInACloneOfThatTreeTest { 
    
    	@Test
    	public void test() { 
    		FindACorrespondingNodeOfABinaryTreeInACloneOfThatTree obj = new FindACorrespondingNodeOfABinaryTreeInACloneOfThatTree();
    
    		TreeNode root1 = BinaryTree.integers2BinaryTree(7,4,3,null,null,6,19);
    		TreeNode clone1 = BinaryTree.integers2BinaryTree(7,4,3,null,null,6,19);
    		
    		
    		assertEquals(3, obj.getTargetCopy(root1, clone1, new TreeNode(3)).val);
    	}
    }

[https_leetcode.com_problems_find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree]: https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/
[4f3f0ce0eae18411919b5680fe461adb.png]: /images/20221005/2ac7661297994a04b1a51539f9528274.png
[a0ad04ad2a7826e8d1ad8cec7a3e1492.png]: /images/20221005/70e9a4c048524aba8c01dfe05c8af6e3.png
[f8776dbe2eb2cdf2c39c03b93462e3a0.png]: /images/20221005/c5986541b54d44c0b1f43df04925bac6.png
[9e904078cc60aea9f95fda44ef215018.png]: /images/20221005/76818d279a0e42948b4338707c1596ac.png
[df30e5dd767aebd29943ad1e862902cb.png]: /images/20221005/aec7fab6e9a2485fa70987d1ba644e52.png