Java 101 Chapter 13

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

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.
Input: tree = [7], target =  7
Output: 7
Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4
Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5
Input: tree = [1,2,null,3], target = 2
Output: 2
/**
* 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) {
//Queue<TreeNode> queue= new LinkedList<>
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(cloned);
while(q.size() > 0){
TreeNode tmp = q.poll();
if( areNodeSame(target, tmp) ) return tmp;
if(tmp.left != null ) q.add(tmp.left);
if(tmp.right != null ) q.add(tmp.right);
}
return null;
}
public boolean areNodeSame(TreeNode node, TreeNode anotherNode){
if(node != null && anotherNode != null && node.val == anotherNode.val ){
if(node.left == null && anotherNode.left != null) return false;
if(node.left != null && anotherNode.left == null) return false;
if(node.left != null && anotherNode.left != null && node.left.val != anotherNode.left.val) return false;

if(node.right == null && anotherNode.right != null) return false;
if(node.right != null && anotherNode.right == null) return false;
if(node.right != null && anotherNode.right != null && node.right.val != anotherNode.right.val) return false;

return true;
}return false;
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store