993. Cousins in Binary Tree #

Problem #

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:

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

Problem Summary #

In a binary tree, the root node is at depth 0, and the children of each node at depth k are at depth k+1. If two nodes in a binary tree have the same depth but different parents, then they are a pair of cousin nodes. We are given the root node root of a binary tree with unique values, as well as the values x and y of two different nodes in the tree. Return true only when the nodes corresponding to values x and y are cousin nodes. Otherwise, return false.

Solution Ideas #

Given a binary tree and two values x and y, determine whether these two values are sibling nodes. Definition of sibling nodes: they are both located on the same level, and their parent node is the same node.
There are 3 solution methods for this problem: DFS, BFS, and recursion. The ideas are not difficult.

Code #


package leetcode

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

// Solution 1: Recursion
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)
}

// Solution 2: 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
}

// Solution 3: 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)
}