樹的 LCA、距離與路徑問題

# LC 236 Lowest Common Ancestor of a Binary Tree
# LC 235 Lowest Common Ancestor of a Binary Search Tree
# (for LC 1650 -- parent pointers, no root -- see the variant below)
# V0
# IDEA : RECURSION + POST ORDER TRANSVERSAL
### NOTE : we need POST ORDER TRANSVERSAL for this problem
#          -> left -> right -> root
#          -> we can make sure that if p == q, then the root must be p and q's "common ancestor"
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        ### NOTE here
        # if not root or find p in tree or find q in tree
        # -> then we quit the recursion and return root
        if not root or p == root or q == root:
            return root
        ### NOTE here
        #  -> not root.left, root.right, BUT left, right
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        ### NOTE here
        # find q and p on the same time -> LCA is the current node (root)
        # if left and right -> p, q MUST in left, right sub tree respectively
        if left and right:
            return root
        ### NOTE here
        # if p, q both in left sub tree or both in right sub tree
        return left if left else right

// java
// algorithm book p. 271
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
    // base case
    if (root == null) return null;
    if (root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // case 1
    if (left != null && right != null){
        return root;
    }
    // case 2
    if (left == null && right == null){
        return null;
    }
    // case 3
    return left == null ? right: left;
}

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):
        # NOTE !!! 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:
            # NOTE !!! `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) {
        // NOTE !!! 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
            # NOTE !!! 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
// 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)

        # NOTE !!! 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]

Standard Tree (Unidirectional)        →    Tree with Parent Map (Bidirectional)

      1                                          1
     / \              Build Parent Map          / \
    2   3             ===============>         2 ← 3
   / \                                        / \
  4   5                                      4 ← 5

Can only go down (left/right)          Can go down (left/right) AND up (parent)

// java
// IDEA: DFS + Parent Map + BFS
/**
 * Why this works?
 *
 * Tree → Graph → BFS (visiting)
 *
 * • From target you need to explore all directions reachable in k steps:
 *   left, right, and up (to parent).
 *   Converting the tree to an undirected graph (children + parent edges)
 *   and then running BFS from target to depth k returns the desired nodes.
 *
 * • visited ensures we don't revisit nodes (which would otherwise make the BFS
 *   incorrect/infinite once parent edges are present).
 */

public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    List<Integer> res = new ArrayList<>();
    // parentMap stores parent pointers for every node (node -> parent)
    Map<TreeNode, TreeNode> parentMap = new HashMap<>();

    if (root == null) return res;

    // Step 1: Build parent map for all nodes
    buildParentMap(root, null, parentMap);

    // Step 2: BFS starting from target, stop at distance k
    Queue<TreeNode> queue = new LinkedList<>();
    Set<TreeNode> visited = new HashSet<>();
    queue.offer(target);
    visited.add(target);
    int dist = 0;

    /**
     * • Each loop iteration processes one BFS "level"
     *   (all nodes at the same distance from target).
     *
     * • If current distance dist equals k, the nodes currently
     *   in queue are exactly the nodes at distance k.
     */
    while (!queue.isEmpty()) {
        int size = queue.size();

        if (dist == k) {
            // Collect all nodes currently in the queue
            for (TreeNode node : queue) {
                res.add(node.val);
            }
            break;
        }

        /**
         * NOTE!!!
         * For each node, we visit cur.left, cur.right, and its parent via BFS
         *
         * • Process the size nodes of the current level:
         *   - For each cur, try to move to cur.left, cur.right, and its parent
         *   - visited.add(node) returns true only if node was not already present
         *     That both checks and marks in one call
         *
         * • After processing the whole level, increment dist and continue
         */
        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.poll();

            // Explore neighbors: left, right, parent
            if (cur.left != null && visited.add(cur.left)) {
                queue.offer(cur.left);
            }
            if (cur.right != null && visited.add(cur.right)) {
                queue.offer(cur.right);
            }
            TreeNode parent = parentMap.get(cur);
            if (parent != null && visited.add(parent)) {
                queue.offer(parent);
            }
        }
        dist++;
    }

    return res;
}

/**
 * NOTE!!! Helper function to build parent map
 *
 * • We need to be able to move upwards from any node (to parent).
 *   A binary tree node only knows left/right children, so we precompute
 *   parents by a DFS.
 *
 * • Simple DFS that records parent of each node (parentMap.put(node, parent))
 * • For root we pass parent = null
 * • After this every node maps to its parent (or null for root)
 */
private void buildParentMap(TreeNode node, TreeNode parent,
                            Map<TreeNode, TreeNode> parentMap) {
    if (node == null) return;

    parentMap.put(node, parent);
    buildParentMap(node.left, node, parentMap);
    buildParentMap(node.right, node, parentMap);
}

# python
# LC 863. All Nodes Distance K in Binary Tree
from collections import defaultdict, deque

def distanceK(root, target, k):
    """
    IDEA: Build bidirectional graph + BFS

    Step 1: DFS to build parent-child bidirectional edges
    Step 2: BFS from target to find all nodes at distance k
    """

    # Build undirected graph
    graph = defaultdict(list)

    def build_graph(parent, child):
        """DFS to build bidirectional edges"""
        if parent and child:
            graph[parent.val].append(child.val)
            graph[child.val].append(parent.val)
        if child.left:
            build_graph(child, child.left)
        if child.right:
            build_graph(child, child.right)

    # Build graph from root
    build_graph(None, root)

    # BFS from target
    queue = deque([(target.val, 0)])
    visited = {target.val}
    result = []

    while queue:
        node_val, dist = queue.popleft()

        if dist == k:
            result.append(node_val)
            continue

        # Explore all neighbors (left, right, parent)
        for neighbor in graph[node_val]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return result

1. Build parent map (DFS preprocessing)
2. Convert tree to undirected graph (children + parent edges)
3. BFS from target node, exploring all neighbors (left, right, parent)
4. Track visited nodes to avoid cycles
5. Stop at desired distance/condition

// java
// LC 1740 Find Distance in a Binary Tree

// V1
/**
 *  IDEA of `getPathLen` help func:
 *
 *  🧠 Summary of Logic Flow
 *  1.  Stop when null (return -1) or when target is found (return distance).
 *  2.  Search left first. If found, return immediately.
 *  3.  Otherwise, search right.
 *  4.  If neither side contains the target, the function will bubble up -1.
 */
private int getPathLen(TreeNode root, int target, int dist) {
    /** NOTE !!!
     *
     *   base case:
     *
     *  •   Base case #1:
     *        if we hit a null node,
     *        -> the target DOES NOT exist in this branch.
     *
     *  •   Returning -1 is a sentinel value
     *      meaning “not found in this subtree”
     */
    if (root == null) {
        return -1;  // not found
    }
    /**
     *  NOTE !!!
     *
     *  •   Base case #2: if the current node matches the target, return dist, which is the current number of edges from the starting node (typically the LCA) to this node.
     *  •   This is the successful termination of the recursion.
     */
    if (root.val == target) {
        return dist;
    }

    /**
     *  NOTE !!!
     *
     *  •   Recurse into the left subtree.
     *  •   Increment dist by 1 because we moved down one level.
     *  •   Store the result in left.
     *        - If target is in this subtree,
     *          left will contain the distance.
     *       - Otherwise, left will be -1.
     */
    int left = getPathLen(root.left, target, dist + 1);
    /**
     *  •   If we found the target in the left subtree,
     *      return that distance immediately.
     *  •   This avoids unnecessary searching in the right subtree.
     */
    if (left != -1) {
        return left;
    }

    /**
     *  NOTE !!!
     *
     *  •   If not found on the left, search the right subtree with dist + 1.
     *  •   Return the result directly:
     *       - Either a valid distance if found,
     *       - Or -1 if not found in right subtree either.
     *
     */
    int right = getPathLen(root.right, target, dist + 1);
    return right;
}
    

// V2
public int findDistance(TreeNode root, int p, int q) {
    TreeNode lca = findLCA(root, p, q);
    return getDistance(lca, p) + getDistance(lca, q);
}

private TreeNode findLCA(TreeNode node, int p, int q) {
    if (node == null || node.val == p || node.val == q) {
        return node;
    }
    TreeNode left = findLCA(node.left, p, q);
    TreeNode right = findLCA(node.right, p, q);

    if (left != null && right != null) return node;
    return left != null ? left : right;
}

private int getDistance(TreeNode node, int target) {
    if (node == null) return -1;
    if (node.val == target) return 0;

    /** NOTE !!! check left BEFORE recursing right -- this is the short-circuit the
     *  walkthrough below describes. Evaluating both first still returns the right
     *  answer, but it visits the whole right subtree after the target was found. */
    int leftDist = getDistance(node.left, target);
    if (leftDist != -1) return leftDist + 1;

    int rightDist = getDistance(node.right, target);
    if (rightDist != -1) return rightDist + 1;
    return -1;
}

# python
# LC 1740 Find Distance in a Binary Tree
class Solution:
    def findDistance(self, root, p, q):
        if p == q or not root:
            return 0
        # Step 1: find the split point (Lowest Common Ancestor)
        lca = self.get_lca(root, p, q)
        # Step 2: measure edge distance from LCA down to each target
        dist_p = self.get_dist(lca, p, 0)
        dist_q = self.get_dist(lca, q, 0)
        # dist is ALWAYS the sum — see the 2 structural cases below
        return dist_p + dist_q

    def get_lca(self, root, p, q):
        if not root:
            return None
        if root.val == p or root.val == q:  # match by VALUE (p, q are ints)
            return root
        left = self.get_lca(root.left, p, q)
        right = self.get_lca(root.right, p, q)
        if left and right:      # p, q split here -> this node is the LCA
            return root
        return left if left else right

    # NOTE !!! below helper func -- pre-order DFS
    def get_dist(self, root, target, dist):
        """
        NOTE !!!
        If not root, we return `-1` (sentinel = "not found in this branch"),
        but NOT `0`, since 0 is also a VALID answer (target found at current node).
        """
        if not root:
            return -1          # <-- sentinel: dead end, target not on this path

        if root.val == target:
            return dist        # <-- found: dist = # edges from LCA to here

        # NOTE !!! the right recursion is INSIDE the else path -- that is what makes
        #          the short-circuit real. Calling both first and then testing `left`
        #          walks the right subtree even when the target was already found.
        left = self.get_dist(root.left, target, dist + 1)
        if left != -1:
            # left subtree found the target -- pass that valid distance up, skip right
            return left

        # Otherwise return whatever the right subtree finds (a valid dist, or -1)
        return self.get_dist(root.right, target, dist + 1)

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
# 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
# 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  ✅

// Template for root-to-leaf path collection (LC 112 / 113 / 257)
void dfs(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> result) {
    if (node == null) return;

    // 1. Pre-order: add current node FIRST
    path.add(node.val);
    remaining -= node.val;

    // 2. Check leaf condition
    if (node.left == null && node.right == null && remaining == 0) {
        result.add(new ArrayList<>(path));  // save a COPY
    } else {
        // 3. Recurse
        dfs(node.left, remaining, path, result);
        dfs(node.right, remaining, path, result);
    }

    // 4. Backtrack: remove current node
    path.remove(path.size() - 1);
}

// LC 257 — Binary Tree Paths (String path, no backtrack)
// Reference: ref_code/interviews-master/leetcode/tree/BinaryTreePaths.java
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) {
    // 1. Leaf check: path is complete
    if (node.left == null && node.right == null) {
        res.add(path);
        return;
    }

    // 2. Traverse Left: path update happens INSIDE the DFS call
    if (node.left != null) {
        /** NOTE !!!
         *  We do `path update` within DFS call itself.
         *  path + "->" + node.left.val creates a NEW string,
         *  so `path` in the current frame is unchanged — no backtrack needed.
         */
        dfs(node.left, path + "->" + node.left.val, res);
    }

    // 3. Traverse Right: same pattern
    if (node.right != null) {
        /** NOTE !!!
         *  Same idea: path is NOT mutated here.
         *  Each branch gets its own copy of the string.
         */
        dfs(node.right, path + "->" + node.right.val, res);
    }
}

// LC 113 — Path Sum II (List path, explicit backtrack)
void dfs(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> result) {
    if (node == null) return;

    path.add(node.val);           // ← mutate shared list
    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: undo mutation
}

# Python equivalent — immutable string path (LC 257)
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))  # new string, no backtrack
        if node.right:
            dfs(node.right, path + "->" + str(node.right.val))
    if root:
        dfs(root, str(root.val))
    return res

curSum - targetSum = ancestorSum
→ if ancestorSum exists in map, a valid sub-path ends at current node

// Template: Pre-order DFS + Prefix Sum HashMap (LC 437)
int count = 0;
Map<Long, Integer> prefixMap = new HashMap<>();

int pathSum(TreeNode root, int targetSum) {
    prefixMap.put(0L, 1);  // base case: empty path has sum 0
    dfs(root, 0L, targetSum);
    return count;
}

void dfs(TreeNode node, long curSum, int targetSum) {
    if (node == null) return;

    // 1. Pre-order: update prefix sum with current node
    curSum += node.val;

    // 2. Check: curSum - targetSum = a previous prefix sum?
    //    → means a valid sub-path ends here
    //    (2-sum trick: curSum - ancestorSum = targetSum)
    count += prefixMap.getOrDefault(curSum - targetSum, 0);

    // 3. Record current prefix sum BEFORE recursing into children
    prefixMap.put(curSum, prefixMap.getOrDefault(curSum, 0) + 1);

    // 4. Recurse (pre-order: process node before children)
    dfs(node.left, curSum, targetSum);
    dfs(node.right, curSum, targetSum);

    // 5. BACKTRACK: remove curSum so sibling branches are not affected
    prefixMap.put(curSum, prefixMap.get(curSum) - 1);
}

# LC 112 Path Sum - Has Path with Target Sum
def hasPathSum(self, root, targetSum):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == targetSum
    return (self.hasPathSum(root.left, targetSum - root.val) or
            self.hasPathSum(root.right, targetSum - root.val))

# LC 113 Path Sum II - All Paths with Target Sum
def pathSum(self, root, targetSum):
    result = []

    def dfs(node, remaining, path):
        if not node:
            return

        path.append(node.val)

        if not node.left and not node.right and remaining == node.val:
            result.append(path[:])

        dfs(node.left, remaining - node.val, path)
        dfs(node.right, remaining - node.val, path)

        path.pop()  # backtrack

    dfs(root, targetSum, [])
    return result

# LC 437 Path Sum III - Number of Paths with Target Sum (any start/end)
def pathSum(self, root, targetSum):
    def dfs(node, current_sum):
        if not node:
            return 0

        current_sum += node.val
        result = prefix_sum.get(current_sum - targetSum, 0)

        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1

        result += dfs(node.left, current_sum)
        result += dfs(node.right, current_sum)

        prefix_sum[current_sum] -= 1
        return result

    prefix_sum = {0: 1}
    return dfs(root, 0)

# LC 543 Diameter of Binary Tree - Longest Path Between Any Two Nodes
def diameterOfBinaryTree(self, root):
    self.diameter = 0

    def dfs(node):
        if not node:
            return 0

        left_depth = dfs(node.left)
        right_depth = dfs(node.right)

        # Update diameter through current node
        self.diameter = max(self.diameter, left_depth + right_depth)

        return 1 + max(left_depth, right_depth)

    dfs(root)
    return self.diameter

# LC 687 Longest Univalue Path - Longest Path with Same Values
def longestUnivaluePath(self, root):
    self.longest = 0

    def dfs(node):
        if not node:
            return 0

        left_length = dfs(node.left)
        right_length = dfs(node.right)

        left_path = left_length + 1 if node.left and node.left.val == node.val else 0
        right_path = right_length + 1 if node.right and node.right.val == node.val else 0

        self.longest = max(self.longest, left_path + right_path)

        return max(left_path, right_path)

    dfs(root)
    return self.longest

// java
// LC 112 Path Sum
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }

    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }

    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
}

// LC 113 Path Sum II
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(root, targetSum, path, 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);

    if (node.left == null && node.right == null && remaining == node.val) {
        result.add(new ArrayList<>(path));
    }

    dfs(node.left, remaining - node.val, path, result);
    dfs(node.right, remaining - node.val, path, result);

    path.remove(path.size() - 1); // backtrack
}

# LeetCode 742. Closest Leaf in a Binary Tree
# V0
# IDEA : DFS build GRAPH + BFS find ans (MOVE PARENT PATTERN)
# See section 2 (Move Parent Pattern) for detailed explanation of this pattern
### NOTE :  closest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.
#         -> We only consider the min distance between left (no sub tree) and k
### NOTE : we need DFS create the graph
# https://www.youtube.com/watch?v=x1wXkRrpavw
# https://blog.csdn.net/qq_17550379/article/details/87778889
import collections
class Solution:
    # build graph via DFS
    # node : current node
    # parent : parent of current node
    def buildGraph(self, node, parent, k):
        if not node:
            return
        # if node.val == k, THEN GET THE start point FROM current "node",
        # then build graph based on above
        if node.val == k:
            self.start = node
        if parent:
            self.graph[node].append(parent)
            self.graph[parent].append(node)
        self.buildGraph(node.left, node, k)
        self.buildGraph(node.right, node, k)

    # search via DFS
    def findClosestLeaf(self, root, k):


        self.start = None
        ### NOTE : we need DFS create the graph
        self.buildGraph(root, None, k)
        q, visited = [root], set()
        #q, visited = [self.start], set() # need to validate this
        self.graph = collections.defaultdict(list)
        while q:
            for i in range(len(q)):
                cur = q.pop(0)
                # add cur to visited, NOT to visit this node again
                visited.add(cur)
                ### NOTICE HERE 
                # if not cur.left and not cur.right: means this is the leaf (HAS NO ANY left/right node) of the tree
                # so the first value of this is what we want, just return cur.val as answer directly
                if not cur.left and not cur.right:
                    # return the answer
                    return cur.val
                # if not find the leaf, then go through all neighbors of current node, and search again
                for node in self.graph:
                    if node not in visited: # need to check if "if node not in visited" or "if node in visited"
                        q.append(node)

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