[LeetCode] binary Tree Cameras

문제링크

Binary Tree Cameras - LeetCode

 

접근 방법

binary tree를 탐색하는 문제이다.
tree 구조에서 임의의 노드에 카메라가 설치되어 있다면 그 노드의 직계 부모, 직계 자손을 모두 모니터링할 수 있다.
이때 트리에서 가장 적게 카메라를 설치하는 경우 카메라는 몇대가 필요한지 구하는 문제이다.

DFS 알고리즘을 통해 가장 깊은 노드(최하단 leaf node)부터 탐색하는 방식으로 진행한다.

dfs를 진행하며 가정할 수 있는 상황은 4가지가 있다.
(covered : 카메라로 모니터링 되는 상태,  notCovered : 모니터링되지 않는 상태, hasCamera : 카메라를 갖는 노드)
1. 매개변수로 주어지는 최하단 node가 falsy(null)일때, covered 상태를 반환
2. 두 자식노드(left, right)가 covered일때 notCovered 상태를 반환
    (깊이 우선이므로 자식이 hasCamera가 아니라면 notCovered일 수 밖에 없다.)
3. 두 자식노드 중 하나라도 notCovered라면 hasCamera 상태를 반환하고 카메라 개수 + 1
    ( 모든 노드가 covered또는 hasCamera여야 하므로 )
4. 두 자식노드 중 하나라도 hasCamera라면 Covered상태를 반환
    (직계 자손이 camera가 있다면 부모도 모니터링 할 수 있다.)

이처럼 dfs를 통해 깊이 우선 순차탐색 방식으로 모든 노드를 탐색할 수 있다.
(참고한 블로그)

 

var minCameraCover = function (root) {
  let count = 0;
  const notCovered = 0;
  const hasCamera = 1;
  const covered = 2;

  function dfs(root) {
    // Recursive termination condition
    if (!root) {
      return covered;
    }

    const left = dfs(root.left);
    const right = dfs(root.right);
    if (left === covered && right === covered) {
      return notCovered;
    } else if (left === notCovered || right === notCovered) {
      count++;
      return hasCamera;
    } else if (left === hasCamera || right === hasCamera) {
      return covered;
    }
  }
  if (dfs(root) === notCovered) {
    count++;
  }

  return count;
};

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}