HàPhan 河

## Problem

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:

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

## Solution

Use level traverse technique
Can solve by using and level array to track level

``````class Solution {
func isCousins(_ root: TreeNode?, _ x: Int, _ y: Int) -> Bool {
if root == nil { return false }
var levels : [[TreeNode]] = [[root!]]

var xParent: TreeNode?
var yParent: TreeNode?

var depth = 0

while depth < levels.count {
var new = [TreeNode]()

for node in levels.last! {
if let left = node.left {
if x == left.val { xParent = node }
if y == left.val { yParent = node }
new.append(left)
}

if let right = node.right {
if x == right.val { xParent = node }
if y == right.val { yParent = node }
new.append(right)
}

if let xParent = xParent, let yParent = yParent, xParent.val != yParent.val {
return true
}
}

if !new.isEmpty {
levels.append(new)
}

xParent = nil
yParent = nil
depth += 1
}

return false
}
}
``````