_993. Cousins in Binary Tree.md

993. Cousins in Binary Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 04, 2024

Last updated : July 04, 2024

---

Related Topics : Tree, Depth-First Search, Breadth-First Search, Binary Tree

Acceptance Rate : 56.72 %

---

Solutions

• e993.py

Python

e993.py

# 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: Optional[TreeNode], x: int, y: int) -> bool:
        # schema: (depth, parent)
        ref = []

        def dfs(curr: Optional[TreeNode], prev: Optional[TreeNode], depth: int = 0) -> None :
            if not curr or len(ref) >= 2 :
                return
            
            if ref and depth > ref[0][0] :
                return

            if curr.val == x :
                ref.append((depth, prev))
            elif curr.val == y :
                ref.append((depth, prev))
            
            depth += 1
            dfs(curr.left, curr, depth)
            dfs(curr.right, curr, depth)
        
        dfs(root, None)

        if len(ref) < 2 :
            return False
        return ref[0][0] == ref[1][0] and ref[0][1] != ref[1][1]