993. 二叉树的堂兄弟节点
题目：
在二叉树中，根节点位于深度 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的整数。
思路：
遍历二叉树，有深度优先搜索和广度优先搜索两种方法，需要注意的是要记录父亲节点和x,y结点的深度Depth。最后比较父亲节点是否不一样，和深度是否一致。
代码（深度优先搜索DFS）：
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func isCousins(root *TreeNode, x int, y int) bool {var xParent, yParent *TreeNodevar xDepth, yDepth intvar xFound, yFound boolvar dfs func(node, parent *TreeNode, depth int)dfs = func(node, parent *TreeNode, depth int){if node == nil{return}if node.Val == x{xParent, xDepth, xFound = parent, depth, true}else if node.Val == y{yParent, yDepth, yFound = parent, depth, true}if xFound && yFound{return}dfs(node.Left, node, depth+1)dfs(node.Right, node, depth+1)}dfs(root, nil, 0)return xParent != yParent && xDepth == yDepth}
结果（DFS）：
代码（广度优先搜素）：
func isCousins(root *TreeNode, x, y int) bool {var xParent, yParent *TreeNodevar xDepth, yDepth intvar xFound, yFound bool// 用来判断是否遍历到 x 或 y 的辅助函数update := func(node, parent *TreeNode, depth int) {if node.Val == x {xParent, xDepth, xFound = parent, depth, true} else if node.Val == y {yParent, yDepth, yFound = parent, depth, true}}type pair struct {node *TreeNodedepth int}q := []pair{{root, 0}}update(root, nil, 0)for len(q) > 0 && (!xFound || !yFound) {node, depth := q[0].node, q[0].depthq = q[1:]if node.Left != nil {q = append(q, pair{node.Left, depth + 1})update(node.Left, node, depth+1)}if node.Right != nil {q = append(q, pair{node.Right, depth + 1})update(node.Right, node, depth+1)}}return xDepth == yDepth && xParent != yParent}
结果：
分析：
两个方法的时间复杂度和空间复杂度都是O(n)