Triangle Rule

01 · Question

Count triples (a, b, c) where a is the LCA of b and c, b and c are at the same depth, and the path to b uses only left edges while the path to c uses only right edges.

02 · Solution

Reference solution

1def triangleRule(root: Optional[TreeNode]) -> int:
2    res = 0
3    def dfs(node: Optional[TreeNode]) -> tuple[int, int]:
4        nonlocal res
5        if not node:
6            return 0, 0
7        leftL, leftR = dfs(node.left)
8        rightL, rightR = dfs(node.right)
9        left_len = 1 + leftL
10        right_len = 1 + rightR
11        res += min(left_len, right_len)
12        return left_len, right_len
13    dfs(root)
14    return res

Aligned Path

Evaluate N-ary Expression Tree