Triangle Rule

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.

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

node

tree=[1, 2, 3, 4, 5, 6, 7]

Step 1 / 3

Step 1:

Compute consecutive left and right chains from each node.

Pointers: node=0

Focus: select @ [0]