[LeetCode] Binary Tree Right Side View - Javascript

Binary Tree Right Side View

[오른쪽 시야에서 트리 보기]

 

제약 조건 

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Example

ex2) Input: root = [1,null,3]
     Output: [1,3]

ex3) Input: root = []
     Output: []

초기 문제 접근 방식

초기엔 문제 설명에 대해 이해가 잘 안가, 예시의 그림을 보고 대충 이해하고 풀었다.
단순히 오른쪽 노드를 모두 출력하는 줄 알고 아래와 같이 문제를 풀었고, 실제로 처음 주어지는 테스트케이스 3개는 풀었지만,
다른 테스트 케이스들은 풀지 못했다.

초기 접근 코드

var rightSideView = function(root) {
    const result = [];
    const queue = [];
    
    if (root === null) return result;
    
    queue.push(root);
    while(queue.length !== 0) {
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let n = queue.shift();
            if (i === size - 1) result.push(n.val);
            if (n.left !== null) queue.push(n.left);
            if (n.right !== null) queue.push(n.right);
        }
    }
    
    return result;
};

다시 생각 해보며

실패한 테스트케이스들을 보며 문제를 다시 이해 할 수 있었다.

위의 그림을 예시로, 만약 1,3,4 중 4가 없다고 가정 해보자.

그럼 리턴해야 할 값은 1,3,5가 된다. 4가 없어짐과 동시에 5가 보여지는것이다.

만약 1,3,4 중 3이 사라지면 1,4,5가 보여야한다. 4의 노드가 3의 자리에 들어가기에 5노드가 보이기 때문이다.

 

문제를 풀이하는데에 접근한 방법은 아래와 같다.

먼저 트리의 왼쪽에 있는 노드를 배열에 넣는다.

이 과정을 반복하며 트리의 왼쪽 끝에 도달 한 다음 값이 없으면 오른쪽 노드의 값으로 덮어 씌운다.

 

맨 왼쪽 노드를 모두 재귀 호출했을 땐
res 배열에 [1,2,5]가 들어가게 되고, 해당 노드가 존재하지 않을 때까지 순회했을 때,
오른쪽 노드를 재귀 호출해서 right 값으로 덮어씌우고 없으면 해당 값 그대로 존재하게 한다.
여기서 배열 3개의 인덱스는 각각의 레벨 0, 1, 2로 해석된다.
즉 현재 트리는 3,4가 존재하기에 기존에 존재하던 2,5는 3,4,로 덮어 쓰기가 되어 [1,3,4]가 된다.

solve 코드

function rightSideView(root) {    
    const res = []
    
    function traverse(node, level) {
        if (node?.val === undefined){
            return null
        } 

        res[level] = node.val
        
        traverse(node.left, level + 1)
        traverse(node.right, level + 1)
    }
    
    traverse(root, 0)
    
    return res
};