199. 바이너리 트리 우측면도

설명:



이진 트리의 루트가 주어지면 오른쪽에 서 있다고 상상하고 위에서 아래로 정렬된 것을 볼 수 있는 노드의 값을 반환합니다.

해결책:



시간 복잡도 : O(n)
공간 복잡도: O(n)

var rightSideView = function(root) {
    const output = [];
    // Return an emtpy array if the root is null
    if(!root) return output
    const queue = [];
    queue.push(root)
    while(queue.length) {
        // Push the first item in the queue to the output array
        // We populate the queue from right most node to left most node
        // Nodes in the front of the queue will be the closest to the right side
        output.push(queue[0].val);
        const levelLength = queue.length;
        // Add nodes into the queue from right to left
        for(let i = 0; i < levelLength; i++) {
            const cur = queue.shift();
            if(cur.right) queue.push(cur.right)
            if(cur.left) queue.push(cur.left)
        }
    }
    return output;
};

좋은 웹페이지 즐겨찾기