993. 二叉树的堂兄弟节点

🟢   🔖  树 深度优先搜索 广度优先搜索 二叉树  🔗 力扣 LeetCode

题目

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the valuesx andy _in the tree arecousins , or _false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3

Output: false

Example 2:

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

Output: true

Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3

Output: false

Constraints:

• The number of nodes in the tree is in the range [2, 100].
• 1 <= Node.val <= 100
• Each node has a unique value.
• x != y
• x and y are exist in the tree.

题目大意

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但父节点不同 ，则它们是一对 堂兄弟节点 。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

示例 1：

输入： root = [1,2,3,4], x = 4, y = 3

输出： false

示例 2：

输入： root = [1,2,3,null,4,null,5], x = 5, y = 4

输出： true

示例 3：


输入： root = [1,2,3,null,4], x = 2, y = 3

输出： false

提示：

• 二叉树的节点数介于 2 到 100 之间。
• 每个节点的值都是唯一的、范围为 1 到 100 的整数。

解题思路

为了判断两个节点是否满足条件，我们可以通过一次深度优先搜索（DFS）或广度优先搜索（BFS）完成以下任务：

1. 记录节点的深度和父节点：

   • 遍历二叉树，找到节点 x 和 y 的深度以及它们的父节点。

2. 判断条件：

   • 如果两个节点的深度相同，并且父节点不同，则返回 true。
   • 否则，返回 false。

复杂度分析

• 时间复杂度:O(n)，其中 n 是树中节点的总数。遍历树的所有节点，每个节点访问一次。
• 空间复杂度:
  • DFS 的空间复杂度为 O(h)，h 是树的高度（递归栈）。
  • BFS 的空间复杂度为 O(w)，w 是树的最大宽度。

代码

DFS

/**
 * @param {TreeNode} root
 * @param {number} x
 * @param {number} y
 * @return {boolean}
 */
var isCousins = function (root, x, y) {
	let xInfo = null,
		yInfo = null;

	const dfs = (node, parent, depth) => {
		if (!node) return;
		if (node.val === x) xInfo = { parent, depth };
		if (node.val === y) yInfo = { parent, depth };
		if (xInfo && yInfo) return;
		dfs(node.left, node, depth + 1);
		dfs(node.right, node, depth + 1);
	};

	dfs(root, null, 0);

	return (
		xInfo &&
		yInfo &&
		xInfo.depth === yInfo.depth &&
		xInfo.parent !== yInfo.parent
	);
};

BFS

/**
 * @param {TreeNode} root
 * @param {number} x
 * @param {number} y
 * @return {boolean}
 */
var isCousins = function (root, x, y) {
	let queue = [[root, null, 0]]; // [node, parent, depth]
	let xInfo = null,
		yInfo = null;

	while (queue.length > 0) {
		const [node, parent, depth] = queue.shift();
		if (node.val === x) xInfo = { parent, depth };
		if (node.val === y) yInfo = { parent, depth };
		if (xInfo && yInfo) break;

		if (node.left) queue.push([node.left, node, depth + 1]);
		if (node.right) queue.push([node.right, node, depth + 1]);
	}

	return (
		xInfo &&
		yInfo &&
		xInfo.depth === yInfo.depth &&
		xInfo.parent !== yInfo.parent
	);
};

相关题目

题号	标题	题解	标签	难度	力扣
102	二叉树的层序遍历	[✓]	树 广度优先搜索 二叉树	🟠	🀄️ 🔗
2641	二叉树的堂兄弟节点 II	[✓]	树 深度优先搜索 广度优先搜索 2+	🟠	🀄️ 🔗