樹的 LCA、距離與路徑問題

# python
# LC 236 - Lowest Common Ancestor of a Binary Tree
# IDEA: post-order; each call reports "a target (or their LCA) is below me";
#       the first node that hears it from both sides is the LCA
# time = O(N), space = O(H)
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q:
            return root                      # a target, or fell off the tree
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:                   # p and q split here -> this node is the LCA
            return root
        return left if left else right       # both on one side: pass that side's answer up

// java
// LC 236 - Lowest Common Ancestor of a Binary Tree
// IDEA: post-order; return the target (or the LCA) found below me, else null
// time = O(N), space = O(H)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) {
        return root;                          // the split point
    }
    return left != null ? left : right;
}

p = 5, q = 1
dfs(3)   not a target
  dfs(5) -> 5 is p, return 5        (5's subtree is never searched)
  dfs(1) -> 1 is q, return 1
  left = 5, right = 1  -> both non-null -> LCA = 3

p = 5, q = 4
dfs(3)
  dfs(5) -> return 5 at once        (4 is below it, unseen)
  dfs(1) -> None
  left = 5, right = None -> pass 5 up -> LCA = 5

root = [3,5,1,6,2,0,8,null,null,7,4],  p = 4,  q = 1

  path(4) : 4 -> 2 -> 5 -> 3      (len 4)
  path(1) : 1 -> 3                (len 2)
                     ^
                     the lists merge here -> LCA = 3

# python
# LC 1650 - Lowest Common Ancestor of a Binary Tree III
# IDEA: SET + walk UP (p has a parent chain, so collect it, then re-walk from q)
# time = O(h), space = O(h)
class Solution(object):
    def lowestCommonAncestor(self, p, q):
        # walk UP via `parent`, there is no root to walk down from
        ancestors = set()
        node = p
        while node:
            ancestors.add(node)
            node = node.parent

        # the FIRST hit going up from q is the LOWEST one
        node = q
        while node:
            if node in ancestors:
                return node
            node = node.parent

        return None

# python
# LC 1650 - Lowest Common Ancestor of a Binary Tree III
# IDEA: 2 POINTERS ON THE PARENT CHAIN ("swap the tails") -- same trick as LC 160
# time = O(h), space = O(1)
class Solution(object):
    def lowestCommonAncestor(self, p, q):
        # edge
        if not p or not q:
            return None

        a, b = p, q
        while a != b:
            # `if a else q`, NOT `a.parent or q`
            a = a.parent if a else q
            b = b.parent if b else p
        return a

// java
// LC 1650 - Lowest Common Ancestor of a Binary Tree III
// IDEA: 2 pointers on the parent chain; swap tails on hitting null
// time = O(h), space = O(1)
public Node lowestCommonAncestor(Node p, Node q) {
    // edge
    if (p == null || q == null) {
        return null;
    }

    Node a = p, b = q;
    while (a != b) {
        // consume the null step itself, so both pointers walk the same distance
        a = (a == null) ? q : a.parent;
        b = (b == null) ? p : b.parent;
    }
    return a;
}

step :  0    1    2     3     4     5    6
a    :  4    2    5     3     null  1    3
b    :  1    3    null  4     2     5    3   -> a == b == 3  ✓

# python
# LC 1644 - Lowest Common Ancestor of a Binary Tree II
# IDEA: 236's post-order, but do NOT return early -- count the hits, then validate
# time = O(N), space = O(H)
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        self.found = 0

        def dfs(node):
            if not node:
                return None
            # recurse FIRST, even if node is p or q (no early return)
            left = dfs(node.left)
            right = dfs(node.right)
            if node == p or node == q:
                self.found += 1
                return node
            if left and right:
                return node
            return left if left else right

        lca = dfs(root)
        # only trust the answer if BOTH targets really exist
        return lca if self.found == 2 else None

# python
# LC 1676 - Lowest Common Ancestor of a Binary Tree IV
# IDEA: 236's post-order against a SET of targets (all nodes guaranteed to exist)
# time = O(N), space = O(H + k)
class Solution(object):
    def lowestCommonAncestor(self, root, nodes):
        targets = set(nodes)

        def dfs(node):
            if not node or node in targets:
                return node
            left = dfs(node.left)
            right = dfs(node.right)
            if left and right:
                return node
            return left if left else right

        return dfs(root)

# python
# LC 235 - Lowest Common Ancestor of a Binary Search Tree
# IDEA: walk DOWN while p, q are on the same side; the first split point is the LCA
# time = O(h), space = O(1)
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        node = root
        while node:
            if p.val < node.val and q.val < node.val:
                node = node.left
            elif p.val > node.val and q.val > node.val:
                node = node.right
            else:
                # split point (or node IS p or q) -> LCA
                return node
        return None

Standard LCA (LC 236)                 Deepest Subtree LCA (LC 865)
-----------------------               --------------------------------
Targets p, q are GIVEN                Targets = nodes at max depth (discovered)
Find where p and q paths meet         Find where left/right deepest paths meet

dfs(node) -> (depth, lca_candidate)
             ^^^^^  ^^^^^^^^^^^^^^^
             max depth      the answer for THIS subtree only
             below node

# pattern skeleton
def dfs(node):
    if not node:
        return (BASE_METRIC, None)

    l_metric, l_ans = dfs(node.left)      # post-order: children FIRST
    r_metric, r_ans = dfs(node.right)

    if l_metric > r_metric:               # one side dominates -> pass its answer up
        return (l_metric + 1, l_ans)
    if r_metric > l_metric:
        return (r_metric + 1, r_ans)
    return (l_metric + 1, node)           # tie -> current node is the meeting point

// java
// LC 865 / LC 1123 — Smallest Subtree with All the Deepest Nodes
// IDEA: post-order DFS returning (lca candidate, depth below); equal depths -> this node
// Same as: LCA of the deepest leaves

// Helper class carries both the LCA candidate and its max depth below
class Result {
    TreeNode node;
    int dist;
    Result(TreeNode node, int dist) {
        this.node = node;
        this.dist = dist;
    }
}

/**
 * time = O(N)
 * space = O(H)  — recursion stack; O(log N) balanced, O(N) skewed
 */
public TreeNode subtreeWithAllDeepest(TreeNode root) {
    return dfs(root).node;
}

private Result dfs(TreeNode node) {
    if (node == null) {
        return new Result(null, 0);
    }

    Result left  = dfs(node.left);
    Result right = dfs(node.right);

    // Case 1: left subtree is deeper — LCA is buried there
    if (left.dist > right.dist) {
        return new Result(left.node, left.dist + 1);
    }

    // Case 2: right subtree is deeper — LCA is buried there
    if (right.dist > left.dist) {
        return new Result(right.node, right.dist + 1);
    }

    // Case 3: equal depth — current node is the LCA of all deepest nodes
    return new Result(node, left.dist + 1);
}

# python
# LC 865 / LC 1123 — Smallest Subtree with All the Deepest Nodes
# IDEA: post-order DFS returning (depth, lca_node)
# time = O(N), space = O(H)
class Solution(object):
    def subtreeWithAllDeepest(self, root):
        return self.helper(root)[1]

    def helper(self, node):
        # base case: null has depth 0 and no LCA
        if not node:
            return (0, None)

        # post-order — children resolved BEFORE the decision
        left_depth, left_node = self.helper(node.left)
        right_depth, right_node = self.helper(node.right)

        # case 1) left deeper -> all deepest nodes on left, keep left's answer
        if left_depth > right_depth:
            return (left_depth + 1, left_node)

        # case 2) right deeper -> all deepest nodes on right, keep right's answer
        if right_depth > left_depth:
            return (right_depth + 1, right_node)

        # case 3) SAME depth -> deepest nodes on both sides -> current node is LCA
        return (left_depth + 1, node)

        [3]          ← left.dist(3) == right.dist(2)? No → left wins
       /   \
     [5]   [1]       ← left.dist(2) == right.dist(1)? No → left wins
    /   \
  [6]  [2]           ← left.dist(0) == right.dist(1)? No → right wins
       /  \
      [7] [4]        ← both null, dist=0 → node [2] is LCA ✓

"smallest subtree containing X"      -> post-order (metric, node)   [LC 865]
"LCA of given nodes p, q"            -> post-order found-or-null     [LC 236]
"LCA but I have no root, only parent" -> walk up both chains (LC 160)  [LC 1650]
"longest/max path through any node"  -> post-order + global var      [LC 543, 124]
"deepest / leftmost / level info"    -> BFS level-order              [LC 513, 199]

# python
# LC 863 - All Nodes Distance K in Binary Tree
# IDEA: record every node's parent, then BFS outward from target over left / right / parent;
#       the queue after k rounds is the answer
# time = O(N), space = O(N)
from collections import deque

class Solution(object):
    def distanceK(self, root, target, k):
        parent = {root: None}                # node -> parent, keyed by node, not by value
        stack = [root]
        while stack:
            node = stack.pop()
            for child in (node.left, node.right):
                if child:
                    parent[child] = node
                    stack.append(child)

        visited = {target}
        queue = deque([target])
        dist = 0
        while queue and dist < k:            # one ring per round
            for _ in range(len(queue)):
                node = queue.popleft()
                for nxt in (node.left, node.right, parent[node]):
                    if nxt and nxt not in visited:
                        visited.add(nxt)
                        queue.append(nxt)
            dist += 1
        return [node.val for node in queue]  # empty if the tree ran out before k

// java
// LC 863 - All Nodes Distance K in Binary Tree
// IDEA: DFS builds node -> parent; BFS from target over left / right / parent, k rounds
// time = O(N), space = O(N)
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    buildParentMap(root, null, parent);

    Set<TreeNode> visited = new HashSet<>();
    Deque<TreeNode> queue = new ArrayDeque<>();
    visited.add(target);
    queue.offer(target);
    int dist = 0;
    while (!queue.isEmpty() && dist < k) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            TreeNode[] neighbours = {node.left, node.right, parent.get(node)};
            for (TreeNode next : neighbours) {
                if (next != null && visited.add(next)) {   // add() is false if already seen
                    queue.offer(next);
                }
            }
        }
        dist++;
    }
    List<Integer> res = new ArrayList<>();
    for (TreeNode node : queue) {
        res.add(node.val);
    }
    return res;
}

private void buildParentMap(TreeNode node, TreeNode par, Map<TreeNode, TreeNode> parent) {
    if (node == null) {
        return;
    }
    parent.put(node, par);                    // the root maps to null
    buildParentMap(node.left, node, parent);
    buildParentMap(node.right, node, parent);
}

round 0   queue [5]
round 1   queue [6, 2, 3]     5's left, right and parent
round 2   queue [7, 4, 1]     6 adds nothing; 2 adds 7, 4; 3 adds 1 (5 is visited)
dist == k -> [7, 4, 1]

# python
# LC 1740 - Find Distance in a Binary Tree
# IDEA: find the split point (LCA), then measure each target's depth below it;
#       get_dist is pre-order, carrying depth down, -1 = "not in this branch"
# time = O(N), space = O(H)
class Solution(object):
    def findDistance(self, root, p, q):
        if p == q:
            return 0
        lca = self.get_lca(root, p, q)
        return self.get_dist(lca, p, 0) + self.get_dist(lca, q, 0)

    def get_lca(self, node, p, q):
        if not node or node.val == p or node.val == q:   # p, q are VALUES here
            return node
        left = self.get_lca(node.left, p, q)
        right = self.get_lca(node.right, p, q)
        if left and right:
            return node
        return left if left else right

    def get_dist(self, node, target, depth):
        if not node:
            return -1                        # dead end: the target is not on this path
        if node.val == target:
            return depth                     # edges from the start node to here
        left = self.get_dist(node.left, target, depth + 1)
        if left != -1:
            return left                      # found on the left: skip the right subtree
        return self.get_dist(node.right, target, depth + 1)

// java
// LC 1740 - Find Distance in a Binary Tree
// IDEA: LCA by value, then depth of p and of q below it; -1 means "not in this subtree"
// time = O(N), space = O(H)
public int findDistance(TreeNode root, int p, int q) {
    if (p == q) {
        return 0;
    }
    TreeNode lca = getLca(root, p, q);
    return getDist(lca, p, 0) + getDist(lca, q, 0);
}

private TreeNode getLca(TreeNode node, int p, int q) {
    if (node == null || node.val == p || node.val == q) {
        return node;
    }
    TreeNode left = getLca(node.left, p, q);
    TreeNode right = getLca(node.right, p, q);
    if (left != null && right != null) {
        return node;
    }
    return left != null ? left : right;
}

private int getDist(TreeNode node, int target, int depth) {
    if (node == null) {
        return -1;
    }
    if (node.val == target) {
        return depth;
    }
    int left = getDist(node.left, target, depth + 1);
    if (left != -1) {
        return left;                          // short-circuit: the right side is never walked
    }
    return getDist(node.right, target, depth + 1);
}

get_lca          -> 3     5 is on the left, 0 on the right
get_dist(3, 5)   -> 1     3 -> 5
get_dist(3, 0)   -> 2     the left subtree returns -1; then 3 -> 1 -> 0
answer           1 + 2 = 3

case 1: p and q are in different subtrees      case 2: one target IS the LCA
                                                        (ancestor of the other)
          LCA                                        p (= LCA)
         /   \                                          \
        p     q                                          ...
                                                           q
   dist = dist_p + dist_q                        dist_p = 0, so dist = dist_q

                      3          <- depth 0  (this is also the LCA of 5 and 0)
                   /     \
                  5       1      <- depth 1
                /   \    /  \
               6     2  0    8   <- depth 2
                    / \
                   7   4         <- depth 3

get_dist(3, 5, 0)                 3 != 5  -> recurse left with depth+1
└── get_dist(5, 5, 1)             5 == 5  -> RETURN 1  ✅
        (right subtree never visited — short-circuited by `if left != -1`)

=> dist_p = 1

get_dist(3, 0, 0)                       3 != 0
│
├── get_dist(5, 0, 1)                   5 != 0
│   ├── get_dist(6, 0, 2)               6 != 0
│   │   ├── get_dist(None, 0, 3) -> -1      ❌ dead end
│   │   └── get_dist(None, 0, 3) -> -1      ❌ dead end
│   │   RETURN -1                            ❌ bubbles up
│   └── get_dist(2, 0, 2)               2 != 0
│       ├── get_dist(7, 0, 3) -> -1 (both children None)   ❌
│       └── get_dist(4, 0, 3) -> -1 (both children None)   ❌
│       RETURN -1                            ❌
│   RETURN -1   <- whole LEFT subtree of 3 says "not here"
│
│   (left == -1, so we DO NOT short-circuit — we must try right)
│
└── get_dist(1, 0, 1)                   1 != 0
    └── get_dist(0, 0, 2)               0 == 0  -> RETURN 2  ✅
    RETURN 2  <- passed up UNCHANGED (no `+1`!)
RETURN 2

=> dist_q = 2

1) depth grows going DOWN      2) the found value flows UP untouched
   (as an argument)               (no accumulation on the way back)

     get_dist(.., depth=0)          RETURN 2  ▲
            │  depth+1                        │  same 2
            ▼                        RETURN 2 ▲
     get_dist(.., depth=1)                    │  same 2
            │  depth+1              RETURN 2  ▲
            ▼                                 │
     get_dist(.., depth=2)  ==  target  ->  emit `depth` (= 2)

            left      right     ->  return        meaning
            ----      -----         ------        -------
            -1        -1        ->  -1            target in NEITHER subtree
            d≥0       (skipped) ->  d             found left (short-circuit)
            -1        d≥0       ->  d             found right

# python
# IDEA: bottom-up -- return 0 at the target, add 1 per edge on the way back up
# time = O(N), space = O(H)
def get_dist(self, node, target):
    if not node:
        return -1
    if node.val == target:
        return 0                 # distance to itself is 0

    _left  = self.get_dist(node.left,  target)
    _right = self.get_dist(node.right, target)

    # If found on the left, add 1 for the current edge and return it
    if _left >= 0:
        return _left + 1

    # If found on the right, add 1 for the current edge and return it
    if _right >= 0:
        return _right + 1

    return -1

        V1 (top-down)                      V3 (bottom-up)
        depth flows DOWN                   +1 flows UP

   3   get_dist(3, .., depth=0)       3   return 1 + 1 = 2   ▲
   |            │                     |                      │  +1
   1   get_dist(1, .., depth=1)       1   return 0 + 1 = 1   ▲
   |            │                     |                      │  +1
   0   match -> return depth = 2      0   match -> return 0  ▲

   answer emitted at the BOTTOM       answer assembled on the WAY BACK

# python
# IDEA: BFS carrying (node, dist); the level a node is popped on is its distance
# time = O(N), space = O(W)  -- W = max tree width
from collections import deque

def get_dist(self, root, target):
    if not root:
        return -1

    q = deque([(root, 0)])   # [node, current_distance]

    while q:
        node, dist = q.popleft()

        if node.val == target:
            return dist      # first hit IS the answer (level == distance)

        if node.left:
            q.append((node.left, dist + 1))
        if node.right:
            q.append((node.right, dist + 1))

    return -1                # scanned everything, target not below `root`

                  3(0)
                /      \
             5(1)      1(1)
            /   \     /   \
          6(2) 2(2) 0(2)  8(2)      <- (n) = dist stored alongside the node

 pop        queue after push                        check
 ----       -------------------                     -----
 (3,0)      [(5,1), (1,1)]                          3 != 0
 (5,1)      [(1,1), (6,2), (2,2)]                   5 != 0
 (1,1)      [(6,2), (2,2), (0,2), (8,2)]            1 != 0
 (6,2)      [(2,2), (0,2), (8,2)]                   6 != 0
 (2,2)      [(0,2), (8,2), (7,3), (4,3)]            2 != 0
 (0,2)      -                                       0 == 0  -> RETURN 2  ✅

# python
# LC 113 - Path Sum II
# IDEA: pre-order DFS; push the node, record a COPY at a matching leaf, pop on the way back
# time = O(N * H), space = O(H)   (output not counted; each kept path costs an O(H) copy)
class Solution(object):
    def pathSum(self, root, targetSum):
        result = []
        path = []

        def dfs(node, remaining):
            if not node:
                return
            path.append(node.val)
            remaining -= node.val
            if not node.left and not node.right and remaining == 0:
                result.append(list(path))    # a copy: `path` keeps changing
            else:
                dfs(node.left, remaining)
                dfs(node.right, remaining)
            path.pop()                       # backtrack: the parent's path again

        dfs(root, targetSum)
        return result

// java
// LC 113 - Path Sum II
// IDEA: pre-order DFS with one shared list; add on entry, copy at a matching leaf, remove on exit
// time = O(N * H), space = O(H)
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, targetSum, new ArrayList<>(), result);
    return result;
}

private void dfs(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> result) {
    if (node == null) {
        return;
    }
    path.add(node.val);
    remaining -= node.val;
    if (node.left == null && node.right == null && remaining == 0) {
        result.add(new ArrayList<>(path));    // save a COPY
    } else {
        dfs(node.left, remaining, path, result);
        dfs(node.right, remaining, path, result);
    }
    path.remove(path.size() - 1);             // backtrack
}

path [5, 4, 11, 7]    remaining -5 at leaf 7     no
pop 7, push 2         [5, 4, 11, 2]  remaining 0 at a leaf  -> record
pop 2, 11, 4          [5]
...                   [5, 8, 4, 5]   remaining 0 at a leaf  -> record
answer [[5, 4, 11, 2], [5, 8, 4, 5]]

# python
# LC 257 - Binary Tree Paths
# IDEA: immutable string path -- the update happens in the call, so nothing to undo
# time = O(N * H), space = O(H^2): each live frame holds its own prefix string (output not counted)
def binaryTreePaths(root):
    res = []

    def dfs(node, path):
        if not node.left and not node.right:
            res.append(path)
            return
        if node.left:
            dfs(node.left, path + "->" + str(node.left.val))    # a new string
        if node.right:
            dfs(node.right, path + "->" + str(node.right.val))

    if root:
        dfs(root, str(root.val))
    return res

// java
// LC 257 - Binary Tree Paths
// IDEA: String path, updated inside the DFS call -> each frame keeps its own copy, no backtrack
// time = O(N * H), space = O(H^2): each live frame holds its own prefix string (output not counted)
public List<String> binaryTreePaths(TreeNode root) {
    List<String> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    dfs(root, String.valueOf(root.val), res);
    return res;
}

private void dfs(TreeNode node, String path, List<String> res) {
    if (node.left == null && node.right == null) {
        res.add(path);                        // the path is complete
        return;
    }
    if (node.left != null) {
        dfs(node.left, path + "->" + node.left.val, res);    // `path` here is unchanged
    }
    if (node.right != null) {
        dfs(node.right, path + "->" + node.right.val, res);
    }
}

# python
# LC 437 - Path Sum III
# IDEA: pre-order DFS carrying the root-to-node sum; count earlier prefixes equal to cur - target,
#       add cur for the children, remove it on the way back
# time = O(N), space = O(N)
from collections import defaultdict

class Solution(object):
    def pathSum(self, root, targetSum):
        prefix = defaultdict(int)
        prefix[0] = 1                        # the empty prefix: paths that start at the root

        def dfs(node, cur):
            if not node:
                return 0
            cur += node.val
            count = prefix[cur - targetSum]  # downward paths that end here
            prefix[cur] += 1                 # visible to my descendants only
            count += dfs(node.left, cur) + dfs(node.right, cur)
            prefix[cur] -= 1                 # leave this branch
            return count

        return dfs(root, 0)

// java
// LC 437 - Path Sum III
// IDEA: 2-sum on the root path: curSum - targetSum seen before -> a sub-path ends here
// time = O(N), space = O(N)
private final Map<Long, Integer> prefix = new HashMap<>();

public int pathSum(TreeNode root, int targetSum) {
    prefix.put(0L, 1);                        // the empty path has sum 0
    return dfs(root, 0L, targetSum);
}

private int dfs(TreeNode node, long cur, int targetSum) {
    if (node == null) {
        return 0;
    }
    cur += node.val;                          // long: the sums overflow int
    int count = prefix.getOrDefault(cur - targetSum, 0);
    prefix.merge(cur, 1, Integer::sum);
    count += dfs(node.left, cur, targetSum) + dfs(node.right, cur, targetSum);
    prefix.merge(cur, -1, Integer::sum);      // backtrack
    return count;
}

node 1   cur 1   look up -2 -> 0              prefix {0:1, 1:1}
node 2   cur 3   look up  0 -> 1  (1 -> 2)    prefix {0:1, 1:1, 3:1}
node 3   cur 6   look up  3 -> 1  (3 alone)   answer 2

# python
# LC 112 - Path Sum
# IDEA: pre-order DFS carrying the remaining sum; a leaf answers, an inner node ORs its children
# time = O(N), space = O(H)
def hasPathSum(root, targetSum):
    if not root:
        return False
    if not root.left and not root.right:          # only a leaf can end the path
        return root.val == targetSum
    remaining = targetSum - root.val
    return hasPathSum(root.left, remaining) or hasPathSum(root.right, remaining)

// java
// LC 112 - Path Sum
// IDEA: carry the remaining sum down; a leaf compares, an inner node ORs its children
// time = O(N), space = O(H)
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    int remaining = targetSum - root.val;
    return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

# python
# LC 129 - Sum Root to Leaf Numbers
# IDEA: pre-order DFS carrying the number built so far; a leaf returns it, a parent adds both sides
# time = O(N), space = O(H)
def sumNumbers(root):
    def dfs(node, number):
        if not node:
            return 0
        number = number * 10 + node.val           # append this digit
        if not node.left and not node.right:
            return number
        return dfs(node.left, number) + dfs(node.right, number)

    return dfs(root, 0)

# python
# LC 124 - Binary Tree Maximum Path Sum
# IDEA: return the best downward arm starting at me; record the path that bends at me in a global
# time = O(N), space = O(H)
def maxPathSum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(0, gain(node.left))            # a negative arm is dropped, not taken
        right = max(0, gain(node.right))
        best = max(best, node.val + left + right) # the path that bends at node
        return node.val + max(left, right)        # only one arm continues upward

    gain(root)
    return best

// java
// LC 124 - Binary Tree Maximum Path Sum
// IDEA: return the best arm, clamped at 0; record node + left + right in a field
// time = O(N), space = O(H)
private int best;

public int maxPathSum(TreeNode root) {
    best = Integer.MIN_VALUE;
    gain(root);
    return best;
}

private int gain(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = Math.max(0, gain(node.left));
    int right = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
}

gain(9)    = 9                    best 9
gain(15)   = 15                   best 15
gain(7)    = 7                    best 15
gain(20)   = 20 + max(15, 7) = 35 best max(15, 20 + 15 + 7) = 42
gain(-10)  = -10 + 35 = 25        best max(42, -10 + 9 + 35) = 42   answer 42

# python
# LC 687 - Longest Univalue Path
# IDEA: return the longest same-value arm going down from me (in edges); record left + right
# time = O(N), space = O(H)
def longestUnivaluePath(root):
    best = 0

    def arm(node):
        nonlocal best
        if not node:
            return 0
        left = arm(node.left)
        right = arm(node.right)
        left = left + 1 if node.left and node.left.val == node.val else 0
        right = right + 1 if node.right and node.right.val == node.val else 0
        best = max(best, left + right)
        return max(left, right)

    arm(root)
    return best

# python
# LC 742 - Closest Leaf in a Binary Tree
# IDEA: one DFS adds every child <-> parent edge and finds node k; BFS from k; first leaf popped wins
# time = O(N), space = O(N)
from collections import defaultdict, deque

def findClosestLeaf(root, k):
    graph = defaultdict(list)
    start = None
    stack = [(root, None)]
    while stack:                                  # build the undirected graph
        node, parent = stack.pop()
        if node.val == k:
            start = node
        if parent:
            graph[node].append(parent)
            graph[parent].append(node)
        for child in (node.left, node.right):
            if child:
                stack.append((child, node))

    queue = deque([start])                        # BFS from k, not from the root
    seen = {start}
    while queue:
        node = queue.popleft()
        if not node.left and not node.right:      # a leaf in the ORIGINAL tree
            return node.val
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append(neighbour)

Root-to-leaf path problem?
  → Pre-order DFS + backtracking
  → Pattern: add node → check leaf → recurse → remove node (backtrack)

Path sum from ANY node to ANY node (downward)?
  → Pre-order DFS + prefix sum HashMap (2-sum trick)
  → Pattern: map.put(0,1) → curSum += val → check (curSum-target) in map
             → add to map → recurse → backtrack (decrement map)

Subtree computation (bottom-up)?
  → Post-order DFS
  → Pattern: recurse left, recurse right → combine at current node

Identify or compare subtrees by structure?
  → Post-order DFS + serialize "val,left,right" + HashMap
  → Pattern: serialize(left) + serialize(right) → build key "val,L,R"
             → map.getOrDefault(key,0) == 1 → duplicate! → add to result
             → map.put(key, count+1) → return key to parent

BST / sorted property?
  → In-order DFS
  → Pattern: recurse left → process node → recurse right