오 트리여... 내가 어찌 당신을 이해하오리까?

트리를 이해하고 싶지만 직관적으로 와 닿지가 않아서 관련 코테 문제가 나오면 또 찾아보고 또 찾아보고 또 찾아보고...
몇 번을 반복해도 잘 이해가 안 간다... 알듯 말듯 미묘하다.
아무래도 실무에서 접할 기회가 적다보니 그만큼 익숙해지지 않는 거겠지?

문제 해석

문제에 대해 이야기 하기전에
요즘 릿코드를 열심히 풀어나가고 있는데
(Difficulty -> Easy, Acceptance -> 내림차순)
Acceptance 87% 즈음에서 이 문제를 만나게 되었다.
난이도가 Medium이 되기전까지는 트리 관련 문제가 안 나올 줄 알았건만 바로 또 나와주시더라.

그래도 이번 문제는 풀이가 직관적인거 같아 기록해두고 한 번씩 찾아와서 봐야겠다.

1. Given two binary trees original and cloned and given a reference to a node target in the original tree.

• 오리지널과 복사품, 두 개의 바이너리 트리를 줄게, 그리고 오리지널 트리를 참조하는 타겟 노드도 줄게 (주지마)

2. The cloned tree is a copy of the original tree.

• 복사품 트리는 오리지널을 복사한거야. (뻔한 말하지마)

3. Return a reference to the same node in the cloned tree.

• 복제 트리에서 똑같이 참조하는 부분을 반환하렴.

4. 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.

• 기억해! 넌 내가 준것들을 바꿀 권한이 없어. 그리고 답은 복제 트리에서 참조한 노드로만 제출해야해.

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.

문제풀이

• 맨 첨에는 4번 문장을 무시하고 바로 아래와 같은 코드를 날렸다.

var getTargetCopy = function(original, cloned, target) {
    return target;
}

• 결과는
  

다른 외국인 친구들의 솔루션을 봐도 잘 이해가 가지 않았다.
그나마 제일 이해가 잘 가는 외국인 친구의 코드를 하나 베껴서 문제를 통과하고, 한 땀 한 땀 그려가며 이해해보기로 했다.

var getTargetCopy = function(original, cloned, target) {
    const Q = [original];
    const cloneQ = [cloned];
    
    while(Q.length > 0) {
        let node = Q.shift();
        let cloneNode = cloneQ.shift();
        if(node == target) return cloneNode;
        if(node.left) {
            Q.push(node.left);
            cloneQ.push(cloneNode.left);
        }
        if(node.right) {
            Q.push(node.right);
            cloneQ.push(cloneNode.right);
        }
    }
}

문제 파헤치기

주석에는 트리 노드가 아래와 같이 구성되어 있다고 했다.

자 이제 문제를 통과한 코드에 맞춰 그려보자

shift() 로 배열 맨 앞 엘리먼트가 사라지면서 Q의 길이는 0이된다. 그러나...

끝까지 봐주셔서
감사합니다.