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.

题目大意

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

解题思路

• 给出一个二叉树，和 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)
}

---