[Binary Tree BFS (Breadth-First Search)] Binary Tree Right Side View

199. Binary Tree Right Side View

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
  if(!root) {
    return [];
  }

  const levels = [];
  const queue = [];

  queue.push(root);

  while(queue.length) {
    const level = [];

    for(let i = queue.length - 1; i >= 0; i--) {
      const node = queue.shift();
      level.push(node.val);

      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
    }

    levels.push(level);
  }

  const ans = [];

  for(const level of levels) {
    ans.push(level.at(-1));
  }

  return ans;
};

bfs로 레벨마다 노드를 집계합니다. 이때, 우측 트리부터 검색을 시작합니다. 이후, 각 레벨 배열의 마지막 요소들을 도출하면 해답입니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using dfs

해답의 전문은 링크를 확인해주세요.

var rightSideView = function(root) {
    const rightValues = []; // return most right values array
	
    traverse(root, 0,rightValues); // recursion call start from level 0
    
	//after recursive completed return the rightValues array
	return rightValues;
};

const traverse = (root, level, rightValues) => {
    if (root === null) return; // if root is null then just return it
    
    //check if there is no value store at this level (the level will represent the index number of the return array), if it is true then we want to add that value to our 'rightValues' array
	//if there is an element at particular index then we will just ignore it
    if (rightValues.length === level) {
        rightValues.push(root.val);
    }
	
    // always add root.right first because we want to find the most righty nodes AND always increment level by 1 
    traverse(root.right, level + 1, rightValues);
    traverse(root.left, level + 1, rightValues);
}

Example 1을 예로

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

rightValues.length === level 때만 노드를 집계합니다. 우측 트리 탐색 시, level 인자를 높이기 때문에 왼쪽 트리의 노드는 집계되지 않습니다.

level: 0, rightValues: 1, 현재 노드: 1
level: 1, rightValues: 1,3, 현재 노드: 3
level: 2, rightValues: 1,3,4, 현재 노드: 4
level: 1, rightValues: 1,3,4, 현재 노드: 2
level: 2, rightValues: 1,3,4, 현재 노드: 5

본 해답은 공간복잡도 측면에서 필자의 해답보다 나은 성능을 보여줍니다.