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

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/

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:

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:

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

Example 3:

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

Example 4:

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

Example 5:

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);
	}
}