Leetcode 993. Cousins in Binary Tree

# Runtime: 24 ms, faster than 96.87% of Python3 online submissions for Cousins in Binary Tree.
# Memory Usage: 13.8 MB, less than 6.12% of Python3 online submissions for Cousins in Binary Tree.

# 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 isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        if not root: return False
        if not root.left and not root.right: return False
        q = [root, None]
        depth = 0
        _dict = {}
        parents = {}
        while q:
            node = q.pop(0)

            if node is None:
                depth += 1
                if q: q.append(None)

            else:
                _dict[node.val] = depth

                if node.left:
                    q.append(node.left)
                    parents[node.left.val] = node.val
                if node.right:
                    q.append(node.right)
                    parents[node.right.val] = node.val

        if _dict[x] == _dict[y] and parents[x] != parents[y]:
            return True
        else:
            return False
        return

https://leetcode.com/problems/cousins-in-binary-tree/submissions/