佛山網(wǎng)站建設哪家公司好怎么創(chuàng)建網(wǎng)站鏈接
原題鏈接:
https://leetcode.cn/problems/cousins-in-binary-tree/
解題思路:
- 使用隊列進行BFS搜索,同時保存每個節(jié)點,以及其深度和父節(jié)點信息。
- 當搜索到
x
和y
時,對比深度和父節(jié)點,如果滿足要求,則表示找到了堂兄弟節(jié)點。
/*** @param {TreeNode} root* @param {number} x* @param {number} y* @return {boolean}*/
var isCousins = function (root, x, y) {// 使用隊列進行BFS搜索,每個元素保存的值是當前節(jié)點、節(jié)點深度、父節(jié)點let queue = [[root, 1, null]]// 保存搜索到的x和y節(jié)點信息let result = []// 不斷搜索直到隊列被清空,表示完成了對二叉樹的搜索。while (queue.length) {// 將隊列元素出隊,獲取相關(guān)信息const [node, depth, parent] = queue.shift()// 當查找到x或y的值時,將相應的信息保存到resultif (node.val === x || node.val === y) {result.push([node, depth, parent])}// 如果result的長度為2,表示已查找到x和yif (result.length === 2) {// 如果x和y的深度相等,父節(jié)點不同,表示找到了堂兄弟節(jié)點if (result[0][1] === result[1][1] && result[0][2] !== result[1][2]) {return true}return false}// 將當前節(jié)點的左右子節(jié)點入隊,繼續(xù)搜索node.left && queue.push([node.left, depth + 1, node])node.right && queue.push([node.right, depth + 1, node])}
};