Aligned Path

Given a binary tree, a node is aligned if its value equals its depth. Return the longest path consisting only of aligned nodes.

1def alignedPath(root: Optional[TreeNode]) -> int:
2    res = 0
3    def dfs(node: Optional[TreeNode], depth: int) -> int:
4        nonlocal res
5        if not node:
6            return 0
7        left = dfs(node.left, depth + 1)
8        right = dfs(node.right, depth + 1)
9        down = 1 + max(left, right) if node.val == depth else 0
10        res = max(res, down)
11        return down
12    dfs(root, 0)
13    return res

Lowest Common Ancestor (With Parent Pointers)

Triangle Rule

node

tree=Array(7)

Step 1 / 3

Step 1:

Compute aligned chains bottom-up while tracking a global maximum.

Pointers: node=0

Focus: select @ [0]