[LeetCode] 993. Cousins in Binary Tree


パラメータxとyが同じ深さであり、異なる親ノードを有するいとこ関係である場合、trueは、
深さが異なる場合や親が同じ場合はfalse
/**
 * 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
 * @param {number} x
 * @param {number} y
 * @return {boolean}
 */
var isCousins = function (root, x, y) {
  const queue = [root];
  while (queue.length) {
    // queue 배열에 있는 노드 수 만큼 반복하려고 queue길이를 size에 담음
    const size = queue.length;
    let foundX = false;
    let foundY = false;
    // queue에는 특정 레벨의 노드들이 다 들어가있는데 그 레벨의 노드들 순회할것임
    // queue에 계속 노드가 추가되지만 size만큼 반복 -> 해당 깊이의 요소만 순회
    for (let i = 0; i < size; i++) {
      const node = queue.shift(); // queue에 앞쪽 노드부터 차례로 빼내서 확인
      if (node.left && node.right) {
        // 좌,우 자식들이 x와 y인지(x,y가 형제인지)
        if (
          (node.left.val === x && node.right.val === y) 
          || (node.left.val === y && node.right.val === x)
        )
          return false; // 부모가 같으면 형제니까 false;
      }
      if (node.val === x) foundX = true; // 특정 레벨의 노드들 순회중이기 때문에 노드들 중 x값 찾으면 true
      if (node.val === y) foundY = true; // y값 찾으면 true
      if (node.left) queue.push(node.left); // 왼쪽 자식노드 있으면 후에 순회하도록 queue에 push
      if (node.right) queue.push(node.right); // 오른 자식노드 있으면 후에 순회하도록 queue에 push
    }
    if (foundX && foundY) return true; // 이번 레벨의 노드들 에서 x, y 다 찾았다? 그것은 x와 y가 사촌이라는 것
  }
  return false; // 한 레벨에 x나 y 둘 중 하나가 없거나 둘 다 없는 경우 false;
};
  • キューを使用してBFS
  • を実現する.
  • 各深さノード巡回