<p>Given the <code>root</code> of a binary tree with unique values and the values of two different nodes of the tree <code>x</code> and <code>y</code>, return <code>true</code> <em>if the nodes corresponding to the values </em><code>x</code><em> and </em><code>y</code><em> in the tree are <strong>cousins</strong>, or </em><code>false</code><em> otherwise.</em></p>

<p>Two nodes of a binary tree are <strong>cousins</strong> if they have the same depth with different parents.</p>

<p>Note that in a binary tree, the root node is at the depth <code>0</code>, and children of each depth <code>k</code> node are at the depth <code>k + 1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/02/12/q1248-01.png" style="width: 304px; height: 270px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4], x = 4, y = 3
<strong>Output:</strong> false
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/02/12/q1248-02.png" style="width: 334px; height: 266px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,null,4,null,5], x = 5, y = 4
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/02/13/q1248-03.png" style="width: 267px; height: 258px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,null,4], x = 2, y = 3
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[2, 100]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 100</code></li>
	<li>Each node has a <strong>unique</strong> value.</li>
	<li><code>x != y</code></li>
	<li><code>x</code> and <code>y</code> are exist in the tree.</li>
</ul>

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    '''
    def __init__(self):
        self.x = None
        self.y = None
        self.xparent = None
        self.yparent = None
        self.xdepth = 0
        self.ydepth = 0
        self.depth = 0
'''
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        '''
        self.x, self.y = x, y
        self.traverse(root, 0, TreeNode())

        if self.xdepth == self.ydepth and self.xparent != self.yparent:
            return True

        return False
    
    def traverse(self, root, depth, parent):

        if not root: return
        if self.xdepth and self.ydepth: return 

        if root.val == self.x:
            self.xdepth = depth
            self.xparent = parent
        if root.val == self.y:
            self.ydepth = depth
            self.yparent = parent
        
        self.traverse(root.left,  depth + 1, root)
        self.traverse(root.right, depth + 1, root)
        
'''
        
        nodes = [root]
        parents = {root.val: -1}

        while nodes:
            if (parents.get(x) is None) ^ (parents.get(y) is None):
                return False

            if (parents.get(x) is not None) and parents.get(x) != parents.get(y):
                return True
            
            sz = len(nodes)
            for _ in range(sz):
                node = nodes.pop(0)
                parents.pop(node.val)

                for child in (node.left, node.right):
                    if not child: continue
                    nodes.append(child)
                    parents[child.val] = node.val
        
        return False

16600