_1530. Number of Good Leaf Nodes Pairs.md

1530. Number of Good Leaf Nodes Pairs

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

Back to top

---

First completed : July 18, 2024

Last updated : July 18, 2024

---

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

Acceptance Rate : 71.9 %

---

Version 1

This one was grossly inefficient since I was doing a semi-brute force method with set comparisons but it passed which is what mattered since I was aiming for time rather than efficiency at the moment.

---

Solutions

• m1530 Daily v1.py

Python

m1530 Daily v1.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 countPairs(self, root: TreeNode, distance: int) -> int:
        paths = []

        def dfs(paths: List[Set[TreeNode]],
                currPath: Set[TreeNode] = set([root]),
                curr: TreeNode = root) -> None :

            if not curr.left and not curr.right :
                paths.append(currPath.copy())
                return

            if curr.left :
                currPath.add(curr.left)
                dfs(paths, currPath, curr.left)
                currPath.remove(curr.left)
            if curr.right :
                currPath.add(curr.right)
                dfs(paths, currPath, curr.right)
                currPath.remove(curr.right)

        dfs(paths)

        counter = 0
        for i in range(len(paths) - 1) :
            for j in range(i + 1, len(paths)) :
                if len(paths[i]) + len(paths[j]) - len(paths[i] & paths[j]) * 2 <= distance :
                    counter += 1
        return counter