[LeetCode] 993. Cousins in Binary Tree
パラメータxとyが同じ深さであり、異なる親ノードを有するいとこ関係である場合、trueは、
深さが異なる場合や親が同じ場合はfalseキューを使用してBFS を実現する.各深さノード巡回
深さが異なる場合や親が同じ場合は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;
};
Reference
この問題について([LeetCode] 993. Cousins in Binary Tree), 我々は、より多くの情報をここで見つけました https://velog.io/@ursr0706/LeetCode-993.-Cousins-in-Binary-Treeテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol