코딩테스트 준비 - Find a Corresponding Node of a Binary Tree in a Clone of That Tree
다시푸는 코딩 테스트 준비 일지
응시 사이트 : LeetCode
문제 : 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
사용언어 : C#
난이도 : 하
풀이시간 : 약 15m
유형 : 완전탐색, 이진트리, 트리, Memory Compare
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.
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
Constraints:
The number of nodes in the
treeis in the range[1, 104].The values of the nodes of the
treeare unique.targetnode is a node from theoriginaltree and is notnull.
Follow up: Could you solve the problem if repeated values on the tree are allowed?
문제 풀이 접근
이 문제는, 이전 문제와 비슷하게 이진트리 노드를 순회하여 타겟과 같은 것을 찾는 문제다.
보통 저런 자료구조가 Clone이 존재하고 찾으라는 내용은 DeepCopy와 관련된 개념이 있다.
같은 값을 가지고 있을때, 같다고 원소를 판단하는 기준이 할당된 주소를 기준으로 비교해서 같은 원소인지 체크하는 방법이라서..
굳이 Clone을 만들어서 비교해서 찾으라는 것은 클래스 원소 자체보단 값으로 비교해서 찾으면 바로 찾을 것 같아서 left,right를 탐색하여 맞는 원소가 존재할 때 반환할 수 있도록 작성했다.
이 문제의 플로우는 별거 없다.
1. Left, Right 를 찾는 함수를 짜고, 재귀적으로 돌린다.
2. 값이 같은 원소가 있다면 정적변수에 넣어서 리턴한다.
3. 정적변수를 리턴한다.
정답 작성 코드 (C#)
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public static TreeNode ret;
public TreeNode GetTargetCopy(TreeNode original, TreeNode cloned, TreeNode target) {
ret = null;
BSTSearchTarget(cloned,target);
return ret;
}
public void BSTSearchTarget(TreeNode root, TreeNode target)
{
if(root == null) return;
if(ret != null) return;
if(root.val == target.val)
{
ret = root;
return;
}
BSTSearchTarget(root.left,target);
BSTSearchTarget(root.right,target);
}
}코드 결과
의문점이 있다. Follow UP의 내용엔 TreeNode가 고유하지 않아도 찾아낼 수 있는가?
였는데, 주소로 비교할 수도 없고, 값으로도 중복되어 어떤것이 맞는지 찾을 수 없는데, 어떻게 찾아야하는 것일까?
뭔가 생각해보면 Origin에서 다시 루프해서 값대로 다 찾은다음에 그 값중 몇번째 원소인지 찾은 다음 값과 몇번째인지 찾으면 대응되는 것을 찾을 수는 있겠다 싶은데, 더 문제 해결이 일반적인 방법이 궁금하다.