DFS — 進階模式

/**
 * Pattern: DFS traversal on one grid while validating against another grid
 * Use case: Count sub-islands, validate subset components, inclusion checking
 * Key insight: Use boolean flag propagation to track whether ALL cells satisfy condition
 *
 * Time: O(m × n) - visit each cell once
 * Space: O(m × n) - recursion stack + visited set
 */
public int countSubComponents(int[][] grid1, int[][] grid2) {
    if (grid2 == null || grid2.length == 0) {
        return 0;
    }

    int rows = grid2.length;
    int cols = grid2[0].length;
    Set<Integer> visited = new HashSet<>();
    int count = 0;

    // Iterate through grid2 to find all components
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            int flatCoord = r * cols + c;

            // Start DFS on unvisited land cells in grid2
            if (grid2[r][c] == 1 && !visited.contains(flatCoord)) {
                // DFS returns true if ALL cells in this component exist in grid1
                if (dfsValidate(grid1, grid2, r, c, visited)) {
                    count++;
                }
            }
        }
    }

    return count;
}

/**
 * DFS with validation: Check if entire component in grid2 is subset of grid1
 * Returns true only if ALL cells in the component satisfy the condition
 */
private boolean dfsValidate(int[][] grid1, int[][] grid2, int r, int c, Set<Integer> visited) {
    int rows = grid2.length;
    int cols = grid2[0].length;
    int flatCoord = r * cols + c;

    // Base cases
    if (r < 0 || r >= rows || c < 0 || c >= cols
        || grid2[r][c] == 0 || visited.contains(flatCoord)) {
        return true; // Empty/visited cells don't violate the condition
    }

    // Mark as visited
    visited.add(flatCoord);

    // Initialize result as true
    boolean isValid = true;

    // Check condition: Does this cell exist in grid1?
    if (grid1[r][c] == 0) {
        isValid = false; // Found a cell in grid2 that's NOT in grid1
    }

    // CRITICAL: Use && with res to propagate validation through entire component
    // Must visit ALL neighbors even if isValid is false (to mark them as visited)
    isValid = dfsValidate(grid1, grid2, r - 1, c, visited) && isValid;
    isValid = dfsValidate(grid1, grid2, r + 1, c, visited) && isValid;
    isValid = dfsValidate(grid1, grid2, r, c - 1, visited) && isValid;
    isValid = dfsValidate(grid1, grid2, r, c + 1, visited) && isValid;

    return isValid;
}

def count_sub_components(grid1, grid2):
    """
    Count components in grid2 that are completely contained in grid1
    """
    if not grid2 or not grid2[0]:
        return 0

    rows, cols = len(grid2), len(grid2[0])
    visited = set()
    count = 0

    def dfs(r, c):
        """
        DFS with validation
        Returns True if entire component is valid
        """
        # Base cases
        if (r < 0 or r >= rows or c < 0 or c >= cols
            or grid2[r][c] == 0 or (r, c) in visited):
            return True

        visited.add((r, c))

        # Check condition
        is_valid = True
        if grid1[r][c] == 0:
            is_valid = False

        # Visit all neighbors (must visit ALL even if invalid)
        is_valid = dfs(r - 1, c) and is_valid
        is_valid = dfs(r + 1, c) and is_valid
        is_valid = dfs(r, c - 1) and is_valid
        is_valid = dfs(r, c + 1) and is_valid

        return is_valid

    # Main loop
    for r in range(rows):
        for c in range(cols):
            if grid2[r][c] == 1 and (r, c) not in visited:
                if dfs(r, c):
                    count += 1

    return count

Problem: Count islands in grid2 that are completely contained in grid1

grid1: [[1,1,1,0,0],    grid2: [[1,1,1,0,0],
        [0,1,1,1,1],            [0,0,1,0,0],
        [0,0,0,0,0],            [0,1,0,0,0],
        [1,0,0,0,0],            [1,0,1,1,0],
        [1,1,0,1,1]]            [0,1,0,1,0]]

Analysis:
- Island 1 in grid2 (top-left): Cells (0,0), (0,1), (0,2), (1,2)
  → Check grid1: All exist? YES → Count it ✓

- Island 2 in grid2 (middle): Cells (2,1)
  → Check grid1: (2,1) = 0 → NOT a sub-island ✗

- Island 3 in grid2 (bottom): Cells (3,0), (3,2), (3,3), (4,1), (4,3)
  → Check grid1: (3,0) = 1, but (4,1) = 1... complex shape
  → Some cells don't match → NOT a sub-island ✗

Result: 1 sub-island (only the first one)

Key Insight:
- Must traverse ENTIRE island in grid2
- Check EVERY cell against grid1
- Return true only if ALL cells pass validation

// CORRECT: Visit all neighbors, accumulate results
res = dfs(r - 1, c) && res;
res = dfs(r + 1, c) && res;
res = dfs(r, c - 1) && res;
res = dfs(r, c + 1) && res;

// WRONG: Short-circuits, doesn't visit all cells
if (!dfs(r - 1, c)) return false;  // Stops early, leaves cells unvisited!

/**
 * Pattern: Build bidirectional graph with direction flags, count edge reversals via DFS
 * Use case: Reorder edges, reverse routes, make all paths lead to a target node
 * Key insight: Treat directed graph as undirected for traversal, but track original directions
 *
 * Time: O(V + E) - visit each node and edge once
 * Space: O(V + E) - adjacency list + visited array
 */
public int minReorder(int n, int[][] connections) {
    // Build bidirectional adjacency list with direction flags
    // Map: city -> List of [neighbor, direction_flag]
    // direction_flag: 1 if original direction (needs reversal)
    // direction_flag: 0 if reverse direction (correct direction)
    Map<Integer, List<int[]>> adj = new HashMap<>();
    for (int i = 0; i < n; i++) {
        adj.put(i, new ArrayList<>());
    }

    for (int[] c : connections) {
        int from = c[0];
        int to = c[1];

        // Original direction: from -> to (flag = 1, needs reversal)
        adj.get(from).add(new int[]{to, 1});

        // Reverse direction: to -> from (flag = 0, correct direction)
        adj.get(to).add(new int[]{from, 0});
    }

    boolean[] visited = new boolean[n];
    int[] count = {0}; // Use array to pass by reference

    // Start DFS from target node (city 0)
    dfsCountReversals(0, adj, visited, count);

    return count[0];
}

/**
 * DFS to count edges that need reversal
 * Increment count when traversing edge with flag=1 (wrong direction)
 */
private void dfsCountReversals(int node, Map<Integer, List<int[]>> adj,
                                boolean[] visited, int[] count) {
    visited[node] = true;

    for (int[] edge : adj.get(node)) {
        int neighbor = edge[0];
        int directionFlag = edge[1];

        if (!visited[neighbor]) {
            // If flag = 1, edge points away from target (needs reversal)
            if (directionFlag == 1) {
                count[0]++;
            }
            dfsCountReversals(neighbor, adj, visited, count);
        }
    }
}

def min_reorder(n, connections):
    """
    Count minimum edge reversals to make all paths lead to node 0
    """
    # Build bidirectional graph with direction flags
    adj = {i: [] for i in range(n)}

    for src, dst in connections:
        # Original direction: src -> dst (flag=1, needs reversal)
        adj[src].append((dst, 1))
        # Reverse direction: dst -> src (flag=0, correct)
        adj[dst].append((src, 0))

    visited = set()
    count = [0]

    def dfs(node):
        visited.add(node)

        for neighbor, flag in adj[node]:
            if neighbor not in visited:
                # If flag=1, edge points away from 0 (needs reversal)
                if flag == 1:
                    count[0] += 1
                dfs(neighbor)

    dfs(0)  # Start from target node
    return count[0]

/**
 * Pattern: Count pairs of nodes that cannot reach each other across different components
 * Use case: Count unreachable/disconnected pairs, isolated node pairs
 * Key insight: For each component, multiply its size by nodes in OTHER components
 *
 * Time: O(V + E) - DFS to find all components
 * Space: O(V) - visited array + adjacency list
 */

// Approach 1: DFS with Forward Counting (count against already processed)
public long countUnreachablePairs_DFS_Forward(int n, int[][] edges) {
    // Build adjacency list
    List<Integer>[] adj = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new ArrayList<>();
    }
    for (int[] edge : edges) {
        adj[edge[0]].add(edge[1]);
        adj[edge[1]].add(edge[0]);
    }

    boolean[] visited = new boolean[n];
    long totalUnreachablePairs = 0;
    long nodesProcessed = 0; // Track nodes in components already processed

    // Find each component and count pairs
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            // DFS to find component size
            long componentSize = dfs(i, adj, visited);

            /**
             * KEY TRICK: Forward counting
             * Each node in current component is unreachable from
             * ALL nodes in previous components
             *
             * Formula: componentSize × nodesProcessed
             * - componentSize: nodes in current component
             * - nodesProcessed: nodes in all previous components
             */
            totalUnreachablePairs += componentSize * nodesProcessed;

            // Update processed count
            nodesProcessed += componentSize;
        }
    }

    return totalUnreachablePairs;
}

private long dfs(int node, List<Integer>[] adj, boolean[] visited) {
    visited[node] = true;
    long count = 1;

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            count += dfs(neighbor, adj, visited);
        }
    }

    return count;
}

// Approach 2: Union-Find with Backward Counting (count against remaining unprocessed)
public long countUnreachablePairs_UnionFind_Backward(int n, int[][] edges) {
    // Initialize Union-Find
    int[] parent = new int[n];
    int[] rank = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    // Union all edges
    for (int[] edge : edges) {
        union(edge[0], edge[1], parent, rank);
    }

    // Count component sizes
    Map<Integer, Integer> sizeMap = new HashMap<>();
    for (int i = 0; i < n; i++) {
        int root = find(i, parent);
        sizeMap.put(root, sizeMap.getOrDefault(root, 0) + 1);
    }

    long result = 0;
    long processed = 0;

    /**
     * KEY TRICK: Backward counting
     * For each component, count pairs with ALL remaining unprocessed nodes
     *
     * Formula: size × (n - size - processed)
     * - size: nodes in current component
     * - n: total nodes
     * - processed: nodes in components already counted
     * - (n - size - processed): nodes in OTHER components not yet counted
     *
     * This avoids double counting by only counting forward to remaining components
     */
    for (int size : sizeMap.values()) {
        result += size * (n - size - processed);
        processed += size;
    }

    return result;
}

private int find(int x, int[] parent) {
    if (parent[x] != x) {
        parent[x] = find(parent[x], parent); // Path compression
    }
    return parent[x];
}

private void union(int x, int y, int[] parent, int[] rank) {
    int rootX = find(x, parent);
    int rootY = find(y, parent);

    if (rootX != rootY) {
        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

// Approach 3: Alternative - Count total pairs minus reachable pairs
public long countUnreachablePairs_Alternative(int n, int[][] edges) {
    // Build adjacency list
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }

    /**
     * Total possible pairs = n × (n-1) / 2
     * Reachable pairs = sum of (componentSize × (componentSize-1) / 2) for each component
     * Unreachable pairs = Total - Reachable
     */
    long totalPairs = (long) n * (n - 1) / 2;
    boolean[] visited = new boolean[n];

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            long size = dfsCount(i, adj, visited);
            // Subtract reachable pairs within this component
            totalPairs -= (size * (size - 1)) / 2;
        }
    }

    return totalPairs;
}

private long dfsCount(int node, List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;
    long count = 1;

    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            count += dfsCount(neighbor, adj, visited);
        }
    }

    return count;
}

def count_unreachable_pairs_dfs(n, edges):
    """
    Count unreachable pairs using DFS with forward counting
    """
    # Build adjacency list
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * n
    total_pairs = 0
    processed = 0

    def dfs(node):
        """DFS to count component size"""
        visited[node] = True
        count = 1
        for neighbor in adj[node]:
            if not visited[neighbor]:
                count += dfs(neighbor)
        return count

    # Find each component
    for i in range(n):
        if not visited[i]:
            component_size = dfs(i)

            # Key trick: multiply by already processed nodes
            total_pairs += component_size * processed
            processed += component_size

    return total_pairs


def count_unreachable_pairs_uf(n, edges):
    """
    Count unreachable pairs using Union-Find with backward counting
    """
    # Initialize Union-Find
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x != root_y:
            parent[root_x] = root_y

    # Union all edges
    for u, v in edges:
        union(u, v)

    # Count component sizes
    from collections import Counter
    size_map = Counter(find(i) for i in range(n))

    result = 0
    processed = 0

    # Key trick: count against remaining unprocessed nodes
    for size in size_map.values():
        result += size * (n - size - processed)
        processed += size

    return result

// java
// LC 332 - Reconstruct Itinerary
// IDEA: Hierholzer — greedy walk consuming edges, append node on dead end, reverse at the end
// time  = O(E log E)   PriorityQueue ordering; each edge is consumed exactly once
// space = O(E)         adjacency map + explicit stack + route
public List<String> findItinerary(List<List<String>> tickets) {
    // min-heap per airport -> always take the smallest lexical destination first
    Map<String, PriorityQueue<String>> graph = new HashMap<>();
    for (List<String> t : tickets) {
        graph.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).add(t.get(1));
    }

    LinkedList<String> route = new LinkedList<>();
    Deque<String> stack = new ArrayDeque<>();
    stack.push("JFK");

    while (!stack.isEmpty()) {
        PriorityQueue<String> pq = graph.get(stack.peek());
        if (pq != null && !pq.isEmpty()) {
            stack.push(pq.poll());        // consume an edge, walk forward
        } else {
            route.addFirst(stack.pop());  // dead end -> finalize (post-order + reverse in one step)
        }
    }
    return route;
}

# python
# LC 332 - Reconstruct Itinerary
# IDEA: Hierholzer — greedy walk consuming edges, append node on dead end, reverse at the end
# time  = O(E log E)   sorting the tickets; each edge is consumed exactly once
# space = O(E)         adjacency lists + explicit stack + route
from collections import defaultdict

def findItinerary(tickets):
    graph = defaultdict(list)
    # sort DESC so list.pop() (from the tail) always yields the smallest airport
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)

    route, stack = [], ["JFK"]
    while stack:
        # walk forward until the current airport has no unused ticket
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())
        # dead end -> this airport is finalized, append in POST-ORDER
        route.append(stack.pop())

    return route[::-1]

# python
# LC 753 - Cracking the Safe
# IDEA: Hierholzer on the de Bruijn graph — node = last (n-1) digits, edge = a full n-digit code
# time = O(k^n), space = O(k^n)
def crackSafe(n, k):
    start = "0" * (n - 1)
    seen, out = set(), []

    def dfs(node):
        for d in map(str, range(k)):
            edge = node + d
            if edge not in seen:
                seen.add(edge)      # consume the EDGE (the code), not the node
                dfs(edge[1:])
                out.append(d)       # post-order append, same as LC 332

    dfs(start)
    return "".join(out) + start

// java
// LC 1192 - Critical Connections in a Network
// IDEA: Tarjan low-link — bridge iff low[child] > disc[parent]
// time  = O(V + E)     single DFS pass
// space = O(V + E)     adjacency list + disc/low arrays + recursion depth
private List<List<Integer>> graph;
private int[] disc, low;
private int timer = 0;
private List<List<Integer>> bridges = new ArrayList<>();

public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (List<Integer> e : connections) {
        graph.get(e.get(0)).add(e.get(1));
        graph.get(e.get(1)).add(e.get(0));
    }
    disc = new int[n];
    low = new int[n];
    Arrays.fill(disc, -1);            // -1 = unvisited
    timer = 0;
    bridges = new ArrayList<>();

    for (int i = 0; i < n; i++) {
        if (disc[i] == -1) dfs(i, -1);   // loop handles a disconnected graph too
    }
    return bridges;
}

private void dfs(int u, int parent) {
    disc[u] = low[u] = timer++;
    for (int v : graph.get(u)) {
        if (v == parent) continue;                 // don't walk straight back up the tree edge
        if (disc[v] == -1) {
            dfs(v, u);
            low[u] = Math.min(low[u], low[v]);     // pull the child's reach up
            if (low[v] > disc[u]) {
                bridges.add(Arrays.asList(u, v));  // no back edge bypasses u-v => bridge
            }
        } else {
            low[u] = Math.min(low[u], disc[v]);    // back edge: use disc[v], NOT low[v]
        }
    }
}

# python
# LC 1192 - Critical Connections in a Network
# IDEA: Tarjan low-link — bridge iff low[child] > disc[parent]
# time  = O(V + E)     single DFS pass
# space = O(V + E)     adjacency list + disc/low arrays + recursion depth
def criticalConnections(n, connections):
    graph = [[] for _ in range(n)]
    for a, b in connections:
        graph[a].append(b)
        graph[b].append(a)

    disc = [-1] * n          # discovery time, -1 = unvisited
    low = [0] * n            # lowest disc reachable from u's subtree via <= 1 back edge
    timer = [0]
    res = []

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        for v in graph[u]:
            if v == parent:
                continue                        # never go straight back up the tree edge
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:            # v's subtree cannot reach u or above
                    res.append([u, v])
            else:
                low[u] = min(low[u], disc[v])   # back edge

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)
    return res

// java
// LC 211 - Design Add and Search Words Data Structure
// IDEA: trie; '.' in a query branches the DFS into every non-null child
// time  = O(L) per addWord; search O(L) with no '.', O(26^d * L) worst case with d dots
// space = O(total chars) for the trie, O(L) recursion depth
class WordDictionary {
    private final WordDictionary[] children = new WordDictionary[26];
    private boolean isWord = false;

    public void addWord(String word) {
        WordDictionary node = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new WordDictionary();
            node = node.children[i];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, this);
    }

    private boolean dfs(String word, int idx, WordDictionary node) {
        if (node == null) return false;                 // guard inside the child
        if (idx == word.length()) return node.isWord;   // NOT `true` — must end a word
        char c = word.charAt(idx);
        if (c == '.') {
            for (WordDictionary child : node.children) {
                if (dfs(word, idx + 1, child)) return true;   // early return on first hit
            }
            return false;
        }
        return dfs(word, idx + 1, node.children[c - 'a']);
    }
}

# python
# LC 211 - Design Add and Search Words Data Structure
# IDEA: dict-based trie; '.' in a query branches the DFS into every child
# time  = O(L) per addWord; search O(L) with no '.', O(26^d * L) worst case with d dots
# space = O(total chars) for the trie, O(L) recursion depth
class WordDictionary:
    def __init__(self):
        self.root = {}

    def addWord(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = True                       # end-of-word marker

    def search(self, word):
        def dfs(node, i):
            if i == len(word):
                return '$' in node             # NOT True — must end a word
            ch = word[i]
            if ch == '.':
                # branch into EVERY child -> this is the DFS part
                for k, child in node.items():
                    if k != '$' and dfs(child, i + 1):
                        return True
                return False
            return ch in node and dfs(node[ch], i + 1)

        return dfs(self.root, 0)

# python
# LC 676 - Implement Magic Dictionary
# IDEA: trie DFS carrying a mismatch budget; must be fully spent at the word end
# time = O(26^1 * L) practically (one mismatch), space = O(total chars)
class MagicDictionary:
    def __init__(self):
        self.root = {}

    def buildDict(self, dictionary):
        self.root = {}
        for w in dictionary:
            node = self.root
            for ch in w:
                node = node.setdefault(ch, {})
            node['$'] = True

    def search(self, searchWord):
        def dfs(node, i, budget):
            if i == len(searchWord):
                return budget == 0 and '$' in node   # EXACTLY one change required
            for ch, child in node.items():
                if ch == '$':
                    continue
                cost = 0 if ch == searchWord[i] else 1
                if cost <= budget and dfs(child, i + 1, budget - cost):
                    return True
            return False

        return dfs(self.root, 0, 1)

// java
// LC 388 - Longest Absolute File Path
// IDEA: stack indexed by depth holds the path length up to each ancestor; popping == returning up
// time  = O(N)   N = input length; every char is scanned a constant number of times
// space = O(D)   D = max nesting depth
public int lengthLongestPath(String input) {
    int maxLen = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);                            // depth 0 has an empty prefix

    for (String line : input.split("\n")) {
        int depth = 0;
        while (depth < line.length() && line.charAt(depth) == '\t') depth++;
        String name = line.substring(depth);

        while (stack.size() > depth + 1) stack.pop();   // unwind to this node's parent

        if (name.contains(".")) {
            maxLen = Math.max(maxLen, stack.peek() + name.length());   // file -> a leaf, score it
        } else {
            stack.push(stack.peek() + name.length() + 1);              // dir  -> +1 for the '/'
        }
    }
    return maxLen;
}

# python
# LC 388 - Longest Absolute File Path
# IDEA: stack indexed by depth holds the path length up to each ancestor; popping == returning up
# time  = O(N)   N = len(input); every char is scanned a constant number of times
# space = O(D)   D = max nesting depth
def lengthLongestPath(input):
    max_len = 0
    stack = [0]                                # stack[d] = prefix length of the dir at depth d

    for line in input.split('\n'):
        name = line.lstrip('\t')
        depth = len(line) - len(name)          # number of leading tabs == depth
        while len(stack) > depth + 1:          # pop back up to this node's parent
            stack.pop()
        if '.' in name:
            max_len = max(max_len, stack[depth] + len(name))     # file: leaf, no '/' suffix
        else:
            stack.append(stack[depth] + len(name) + 1)           # dir: +1 for the '/'

    return max_len

# python
# LC 1233 - Remove Sub-Folders from the Filesystem
# IDEA: build a path trie, then DFS and cut the branch at the first stored folder
# time = O(total path chars), space = O(total path chars)
def removeSubfolders(folder):
    root = {}
    for f in folder:
        node = root
        for part in f.split('/')[1:]:          # [0] is the empty string before the leading '/'
            node = node.setdefault(part, {})
        node['$'] = f                          # store the full path at its terminal node

    res = []

    def dfs(node):
        if '$' in node:
            res.append(node['$'])
            return                             # CUT: anything deeper is a sub-folder
        for k, child in node.items():
            dfs(child)

    dfs(root)
    return res

# python — Post-order distance-bucket aggregation (LC 1530)
# time  = O(N * distance^2)   distance^2 from the d1/d2 double loop per node
# space = O(N)                recursion depth + O(distance) bucket per frame
class Solution:
    def countPairs(self, root, distance):
        self.ans = 0

        def post_order(node):
            # cnt[d] = number of leaves exactly d edges below `node`
            if not node:
                return [0] * (distance + 1)
            if not node.left and not node.right:      # leaf: distance 0 to itself
                base = [0] * (distance + 1)
                base[0] = 1
                return base

            left  = post_order(node.left)
            right = post_order(node.right)

            # (1) join a left-leaf and a right-leaf THROUGH this node (their LCA)
            for d1 in range(distance + 1):
                for d2 in range(distance + 1):
                    if d1 + d2 + 2 <= distance:       # +2 for the two edges via node
                        self.ans += left[d1] * right[d2]

            # (2) shift up by 1 edge for the parent's view
            cur = [0] * (distance + 1)
            for d in range(distance):                 # d+1 must stay in bounds
                cur[d + 1] = left[d] + right[d]
            return cur

        post_order(root)
        return self.ans

ownDuration = (latest - earliest) + baseTime[node]
finishTime  = latest + ownDuration

# python — N-ary tree post-order child min/max rollup (LC 3965)
# time  = O(N)   visit each node once
# space = O(N)   adjacency list + recursion depth
from collections import defaultdict

class Solution:
    def finishTime(self, n, edges, baseTime):
        graph = defaultdict(list)
        for u, v in edges:          # u is PARENT of v
            graph[u].append(v)

        def dfs(node):
            # base case: leaf = no children in the graph
            if not graph[node]:
                return baseTime[node]

            earliest, latest = float('inf'), float('-inf')
            for child in graph[node]:        # loop ALL children (N-ary)
                t = dfs(child)               # value bubbles up from child
                earliest = min(earliest, t)
                latest   = max(latest, t)

            own_duration = (latest - earliest) + baseTime[node]
            return latest + own_duration     # return THIS node's value to parent

        return dfs(0)                        # tree rooted at task 0

// java — same rollup, written ITERATIVELY (see the depth gotcha below)
// time = O(N), space = O(N)
public long finishTime(int n, int[][] edges, int[] baseTime) {

    List<List<Integer>> children = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        children.add(new ArrayList<>());
    }
    for (int[] e : edges) {
        children.get(e[0]).add(e[1]);   // e[0] is PARENT of e[1]
    }

    // push pre-order, drain in reverse -> every child settles before its parent
    Deque<Integer> stack = new ArrayDeque<>();
    Deque<Integer> order = new ArrayDeque<>();
    stack.push(0);
    while (!stack.isEmpty()) {
        int cur = stack.pop();
        order.push(cur);
        for (int c : children.get(cur)) {
            stack.push(c);
        }
    }

    long[] finish = new long[n];        // long, NOT int — see the overflow gotcha
    while (!order.isEmpty()) {
        int cur = order.pop();

        if (children.get(cur).isEmpty()) {
            finish[cur] = baseTime[cur];
            continue;
        }

        long earliest = Long.MAX_VALUE, latest = Long.MIN_VALUE;
        for (int c : children.get(cur)) {
            earliest = Math.min(earliest, finish[c]);
            latest   = Math.max(latest,   finish[c]);
        }

        long ownDuration = (latest - earliest) + baseTime[cur];
        finish[cur] = latest + ownDuration;
    }

    return finish[0];
}

depth[x] = 1                        if parent[x] == -1     (root)
depth[x] = depth[parent[x]] + 1     otherwise

# python — parent-array tree: memoized depth climb (LC 4015)
# time  = O(N)   each node's depth is computed once; each up-edge walked once amortized
# space = O(N)   depth memo + recursion depth (worst case a path-shaped tree)
class Solution:
    def weightedSum(self, parent, nums):
        n = len(parent)
        depth = [0] * n              # 0 == "not computed" (depths are 1-based)

        def get_depth(x):
            if depth[x]:             # memo hit -> stop climbing
                return depth[x]
            if parent[x] == -1:      # root
                depth[x] = 1
            else:
                depth[x] = get_depth(parent[x]) + 1
            return depth[x]

        for i in range(n):           # fill the whole memo
            get_depth(i)

        h = max(depth)               # height = deepest depth
        return sum(nums[i] * (h - depth[i] + 1) for i in range(n))

# python — same memo, no recursion
# time = O(N), space = O(N)
def get_depth(x, parent, depth):
    stack = []
    while depth[x] == 0:             # climb until a computed node (or the root)
        if parent[x] == -1:
            depth[x] = 1
            break
        stack.append(x)
        x = parent[x]
    d = depth[x]
    while stack:                     # unwind: fill every node on the climbed chain
        d += 1
        depth[stack.pop()] = d
    return d

// Java DFS with Stack
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    // Process node
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
}

// Graph DFS with adjacency list
void dfs(int node, boolean[] visited, List<List<Integer>> adj) {
    visited[node] = true;
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, adj);
        }
    }
}

# Using collections.deque as stack
from collections import deque
stack = deque([root])
while stack:
    node = stack.pop()  # pop() for stack behavior
    # Process node

# Graph representation
graph = defaultdict(list)  # Adjacency list
visited = set()  # Track visited nodes

# Recursion limit for deep trees
import sys
sys.setrecursionlimit(10000)

// Pattern: Create placeholder → Pass to DFS → Use modified result

Set<String> uniqueIslands = new HashSet<>();

for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
        if (grid[r][c] == 1) {
            // 1. Create empty StringBuilder placeholder
            StringBuilder pathSignature = new StringBuilder();

            // 2. Pass to DFS — DFS will modify it in place
            dfs(grid, r, c, pathSignature, 'S');

            // 3. After DFS returns, pathSignature is populated
            //    Add the modified result to set
            if (pathSignature.length() > 0) {
                uniqueIslands.add(pathSignature.toString());
            }
        }
    }
}

private void dfs(int[][] grid, int r, int c, StringBuilder path, char direction) {
    // Base case
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0) {
        return;
    }

    // Mark as visited
    grid[r][c] = 0;

    // ✅ MODIFY the reference: append to StringBuilder
    //    This change persists in the caller's pathSignature object
    path.append(direction);

    // Explore neighbors in fixed order
    dfs(grid, r + 1, c, path, 'D');  // Down
    dfs(grid, r - 1, c, path, 'U');  // Up
    dfs(grid, r, c + 1, path, 'R');  // Right
    dfs(grid, r, c - 1, path, 'L');  // Left

    // Backtrack: remove the character added in this call
    path.append('O');  // Backtrack marker
}

Memory Model:

Main stack frame:
├── pathSignature = StringBuilder{} (heap object at address 0x1000)
└── call dfs(..., pathSignature, 'S')

    DFS stack frame 1:
    ├── path = reference to 0x1000 (SAME object!)
    ├── path.append('S')  → 0x1000 now contains "S"
    └── call dfs(..., path, 'D')

        DFS stack frame 2:
        ├── path = reference to 0x1000 (still SAME object!)
        ├── path.append('D')  → 0x1000 now contains "SD"
        └── return

    Back in frame 1:
    ├── path.append('O')  → 0x1000 now contains "SDO"
    └── return

Back in main:
└── pathSignature = StringBuilder{"SDO"}  ✅ (modified!)

// ❌ WRONG: Primitive won't persist changes
private void dfs(int curSum) {
    curSum++;  // Only affects local copy
}

int mySum = 5;
dfs(mySum);
System.out.println(mySum);  // Still 5, NOT 6!

// ✅ CORRECT: Use reference type or return value
private void dfs(StringBuilder path) {
    path.append('D');  // Affects original StringBuilder
}

StringBuilder myPath = new StringBuilder();
dfs(myPath);
System.out.println(myPath);  // Modified! ✅