0993. Cousins in Binary Tree

# 993. Cousins in Binary Tree#

## 题目 #

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

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

We are given the `root` of a binary tree with unique values, and the values `x` and `y` of two different nodes in the tree.

Return `true` if and only if the nodes corresponding to the values `x` and `y` are cousins.

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
``````

Note:

1. The number of nodes in the tree will be between `2` and `100`.
2. Each node has a unique integer value from `1` to `100`.

## 解题思路 #

• 给出一个二叉树，和 x ，y 两个值，要求判断这两个值是不是兄弟结点。兄弟结点的定义：都位于同一层，并且父结点是同一个结点。
• 这一题有 3 种解题方法，DFS、BFS、递归。思路都不难。

## 代码 #

``````
package leetcode

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

// 解法一 递归
func isCousins(root *TreeNode, x int, y int) bool {
if root == nil {
return false
}
levelX, levelY := findLevel(root, x, 1), findLevel(root, y, 1)
if levelX != levelY {
return false
}
return !haveSameParents(root, x, y)
}

func findLevel(root *TreeNode, x, level int) int {
if root == nil {
return 0
}
if root.Val != x {
leftLevel, rightLevel := findLevel(root.Left, x, level+1), findLevel(root.Right, x, level+1)
if leftLevel == 0 {
return rightLevel
}
return leftLevel
}
return level
}

func haveSameParents(root *TreeNode, x, y int) bool {
if root == nil {
return false
}
if (root.Left != nil && root.Right != nil && root.Left.Val == x && root.Right.Val == y) ||
(root.Left != nil && root.Right != nil && root.Left.Val == y && root.Right.Val == x) {
return true
}
return haveSameParents(root.Left, x, y) || haveSameParents(root.Right, x, y)
}

// 解法二 BFS
type mark struct {
prev  int
depth int
}

func isCousinsBFS(root *TreeNode, x int, y int) bool {
if root == nil {
return false
}
queue := []*TreeNode{root}
visited := [101]*mark{}
visited[root.Val] = &mark{prev: -1, depth: 1}

for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
depth := visited[node.Val].depth
if node.Left != nil {
visited[node.Left.Val] = &mark{prev: node.Val, depth: depth + 1}
queue = append(queue, node.Left)
}
if node.Right != nil {
visited[node.Right.Val] = &mark{prev: node.Val, depth: depth + 1}
queue = append(queue, node.Right)
}
}
if visited[x] == nil || visited[y] == nil {
return false
}
if visited[x].depth == visited[y].depth && visited[x].prev != visited[y].prev {
return true
}
return false
}

// 解法三 DFS
func isCousinsDFS(root *TreeNode, x int, y int) bool {
var depth1, depth2, parent1, parent2 int
dfsCousins(root, x, 0, -1, &parent1, &depth1)
dfsCousins(root, y, 0, -1, &parent2, &depth2)
return depth1 > 1 && depth1 == depth2 && parent1 != parent2
}

func dfsCousins(root *TreeNode, val, depth, last int, parent, res *int) {
if root == nil {
return
}
if root.Val == val {
*res = depth
*parent = last
return
}
depth++
dfsCousins(root.Left, val, depth, root.Val, parent, res)
dfsCousins(root.Right, val, depth, root.Val, parent, res)
}

``````

Apr 8, 2023