难度: Easy
在二叉树中，根节点位于深度 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 的整数。
运行时间: 14 ms
内存: 16.1 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
x_parent, x_depth, x_found = None, None, False
y_parent, y_depth, y_found = None, None, False
def dfs(node:TreeNode, depth:int, parent:TreeNode):
if not node:
return
nonlocal x_parent, y_parent, x_depth, y_depth, x_found, y_found
if node.val == x:
x_parent, x_depth, x_found = parent, depth, True
elif node.val == y:
y_parent, y_depth, y_found = parent, depth, True
if x_found and y_found:
return
dfs(node.left, depth+1, node)
if x_found and y_found:
return
dfs(node.right, depth+1, node)
dfs(root, 0, None)
return x_depth == y_depth and x_parent != y_parent
该题解使用了深度优先搜索（DFS）来查找二叉树中的两个节点x和y。通过递归地遍历整个树，它记录下每个节点的父节点和深度。一旦找到与x或y值匹配的节点，它将记录该节点的父节点和深度。最终，如果x和y的深度相同但父节点不同，说明它们是堂兄弟节点，返回true；否则返回false。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
x_parent, x_depth, x_found = None, None, False
y_parent, y_depth, y_found = None, None, False
def dfs(node:TreeNode, depth:int, parent:TreeNode):
if not node:
return
nonlocal x_parent, y_parent, x_depth, y_depth, x_found, y_found
if node.val == x:
x_parent, x_depth, x_found = parent, depth, True
elif node.val == y:
y_parent, y_depth, y_found = parent, depth, True
if x_found and y_found:
return
dfs(node.left, depth+1, node)
if x_found and y_found:
return
dfs(node.right, depth+1, node)
dfs(root, 0, None)
return x_depth == y_depth and x_parent != y_parent
在DFS函数中，通过使用两个非局部变量x_found和y_found来跟踪是否已找到x和y节点。一旦这两个节点都被找到，x_found和y_found将被设置为True。在每次递归调用后，会检查这两个变量，如果它们都为True，递归函数将不再进行更深层的递归调用，从而停止进一步的搜索。这是通过在每次递归进入左或右子树前后进行检查实现的。
没有必要遍历整棵树。在题解中的实现中，一旦x和y都被发现，通过检查x_found和y_found的状态，递归调用就会提前终止，从而避免了不必要的遍历。这样做提高了效率，尤其是在x和y位于树的较浅部分时。
在Python中，`nonlocal`关键字用于在函数或其他作用域中修改外部作用域（非全局）的变量。题解中的`nonlocal`关键字用于允许dfs函数内部修改外层函数isCousins中定义的变量x_parent, y_parent, x_depth, y_depth, x_found, y_found。如果没有使用`nonlocal`，这些变量将被视为局部变量，从而无法更新它们的实际值。
使用外部变量而不是返回值来传递找到的节点信息，可以更简洁地处理多个变量的同时更新。如果使用返回值，每次递归调用都需要返回多个值并在每个递归层级处理这些返回值，这可能会使代码更加复杂和难以理解。通过更新外部变量，可以直接在需要的地方修改和检查这些变量的状态，这使得管理状态和控制递归流程更为直接和清晰。