DFS（深度優先搜尋）

# python
# LC 94 - Binary Tree Inorder Traversal
# IDEA: recurse left, visit, recurse right; move `result.append` to get pre- or post-order
# time = O(n), space = O(h)   h = tree height, the recursion depth
def inorderTraversal(root):
    result = []

    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)          # inorder: between the two children
        dfs(node.right)

    dfs(root)
    return result


def inorderTraversal_iterative(root):
    # the problem's follow-up: an explicit stack replaces the call stack
    result, stack = [], []
    node = root
    while node or stack:
        while node:                      # walk as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()               # the leftmost node not yet visited
        result.append(node.val)
        node = node.right                # then its right subtree
    return result

// java
// LC 94 - Binary Tree Inorder Traversal
// IDEA: recurse left, visit, recurse right; move `result.add` to get pre- or post-order
// time = O(n), space = O(h)
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    dfs(root, result);
    return result;
}

private void dfs(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    dfs(node.left, result);
    result.add(node.val);                // inorder: between the two children
    dfs(node.right, result);
}

LC 101 trace — root = [1,2,2,null,3,null,3]     helper(a, b) pairs  a.left <-> b.right
                                                                   a.right <-> b.left
        1               helper(a=2, b=2)                  vals equal -> descend
      /   \             |- helper(a.left=null, b.right=3)  exactly one null -> FALSE
    2       2           |- (never evaluated: `and` short-circuits)
     \       \
      3       3         answer = False
   a.right  b.right     <- both 3's are RIGHT children, so they are not mirror partners

straight pairing (a.left<->b.left, a.right<->b.right) on the same two inputs:

  [1,2,2,null,3,null,3]   null==null, then 3==3  -> True    (correct answer: False)
  [1,2,2,3,4,4,3]         3 vs 4                 -> False   (correct answer: True)

# python
# LC 101 - Symmetric Tree
# IDEA: paired (dual-pointer) DFS; recurse on the MIRROR pairing (a.left, b.right) / (a.right, b.left)
# time = O(n), space = O(h)   # h = tree height, worst O(n)
class Solution:
    def isSymmetric(self, root):
        if not root:
            return True
        # the helper takes TWO nodes -> the root is never compared to anything
        return self.helper(root.left, root.right)

    def helper(self, left, right):
        if not left and not right:      # both empty -> mirrored
            return True
        if not left or not right:       # exactly one empty -> not mirrored
            return False
        if left.val != right.val:
            return False
        return (
            self.helper(left.left, right.right)     # outer pair
            and
            self.helper(left.right, right.left)     # inner pair
        )

// java
// LC 101 - Symmetric Tree
// IDEA: paired (dual-pointer) DFS; recurse on the MIRROR pairing
// time = O(n), space = O(h)
public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    return helper(root.left, root.right);
}

private boolean helper(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null) {
        return false;
    }
    if (left.val != right.val) {
        return false;
    }
    return helper(left.left, right.right)      // outer pair
            && helper(left.right, right.left); // inner pair
}

# python
# LC 101 - Symmetric Tree (iterative — the stated follow-up)
# IDEA: same mirror pairing, kept on an explicit stack; pop two entries = pop one pair
# time = O(n), space = O(n)
def isSymmetric(root):
    if not root:
        return True
    stack = [root.left, root.right]
    while stack:
        p, q = stack.pop(), stack.pop()          # pops ONE pair
        if not p and not q:
            continue
        if not p or not q or p.val != q.val:
            return False
        # push the two mirror pairs
        stack.append(p.left)
        stack.append(q.right)                    # outer pair
        stack.append(p.right)
        stack.append(q.left)                     # inner pair
    return True

# python
# LC 200 - Number of Islands
# IDEA: scan the grid; each '1' still standing starts a DFS that sinks its island -> count the launches
# time = O(m * n), space = O(m * n)   the recursion is as deep as the largest island
def numIslands(grid):
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return                        # off the grid, water, or already sunk
        grid[r][c] = '0'                  # mark BEFORE recursing, so no cell is entered twice
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                islands += 1              # the first cell of a new island
                sink(r, c)
    return islands

// java
// LC 200 - Number of Islands
// IDEA: scan the grid; each '1' still standing starts a DFS that sinks its island -> count the launches
// time = O(m * n), space = O(m * n)
public int numIslands(char[][] grid) {
    int islands = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {
                islands++;                // the first cell of a new island
                sink(grid, r, c);
            }
        }
    }
    return islands;
}

private void sink(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') {
        return;
    }
    grid[r][c] = '0';                     // mark BEFORE recursing
    sink(grid, r + 1, c);
    sink(grid, r - 1, c);
    sink(grid, r, c + 1);
    sink(grid, r, c - 1);
}

# python
# LC 419 - Battleships in a Board
# IDEA: count only the top-left cell of each ship -> no visited set needed
# time = O(M*N), space = O(1)
def countBattleships(board):
    count = 0
    for r in range(len(board)):
        for c in range(len(board[0])):
            if board[r][c] != 'X':
                continue
            if r > 0 and board[r - 1][c] == 'X':
                continue
            if c > 0 and board[r][c - 1] == 'X':
                continue
            count += 1
    return count

// java
// LC 419 - Battleships in a Board
// IDEA: a cell starts a NEW ship iff it is 'X' and has no 'X' above and no 'X' to its left
// time = O(M*N), space = O(1)
public int countBattleships(char[][] board) {
    int count = 0;
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            if (board[r][c] != 'X') continue;
            if (r > 0 && board[r - 1][c] == 'X') continue;   // continuation of a vertical ship
            if (c > 0 && board[r][c - 1] == 'X') continue;   // continuation of a horizontal ship
            count++;
        }
    }
    return count;
}

# python
# LC 112 - Path Sum
# IDEA: pass the remaining sum down; at a leaf it must be exactly 0; return True as soon as a child does
# time = O(n), space = O(h)
def hasPathSum(root, targetSum):
    if not root:
        return False
    remaining = targetSum - root.val
    if not root.left and not root.right:      # a leaf: the path ends here
        return remaining == 0
    return hasPathSum(root.left, remaining) or hasPathSum(root.right, remaining)

// java
// LC 112 - Path Sum
// IDEA: pass the remaining sum down; at a leaf it must be exactly 0; return true as soon as a child does
// time = O(n), space = O(h)
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    int remaining = targetSum - root.val;
    if (root.left == null && root.right == null) {   // a leaf: the path ends here
        return remaining == 0;
    }
    return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

# python
# LC 113 - Path Sum II
# IDEA: carry the path down; copy it at a matching leaf; pop on the way back up
# time = O(n * h), space = O(h)   copying a path of length h at each matching leaf
def pathSum(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(path[:])               # a copy: path keeps changing
        dfs(node.left, remaining)
        dfs(node.right, remaining)
        path.pop()                               # undo before returning to the parent

    dfs(root, targetSum)
    return result

// java
// IDEA: WRONG — the child's result is ignored, so a path that was found is thrown away
// time = O(V + E), space = O(V)
private boolean dfsPathVisitor(int node, int destination, Map<Integer, List<Integer>> map, boolean[] visited) {
    if (node == destination) return true;
    visited[node] = true;
    for (int next : map.get(node)) {
        if (!visited[next]) {
            dfsPathVisitor(next, destination, map, visited);   // result dropped
        }
    }
    return false;   // false for every node except the destination itself
}

// java
// IDEA: RIGHT — return true as soon as any child reaches the destination
// time = O(V + E), space = O(V)
private boolean dfsPathVisitor(int node, int destination, Map<Integer, List<Integer>> map, boolean[] visited) {
    if (node == destination) return true;
    visited[node] = true;
    for (int next : map.get(node)) {
        if (!visited[next] && dfsPathVisitor(next, destination, map, visited)) {
            return true;    // found one path - that is enough
        }
    }
    return false;           // only after every neighbour has failed
}

Graph: 0 -- 1 -- 2 -- 3        find a path 0 -> 3
       |         |
       4 ------- 5

dfs(0) -> dfs(1) -> dfs(2) -> dfs(3) returns TRUE
WRONG: dfs(2) ignores it, tries 5 (a dead end), returns FALSE; so do dfs(1) and dfs(0)
RIGHT: dfs(2), dfs(1) and dfs(0) each return TRUE at once; 5 and 4 are never tried

# python
# LC 46 - Permutations
# IDEA: choose an unused number, recurse, un-choose; a full-length path is one permutation
# time = O(n * n!), space = O(n)   n! leaves, each copied in O(n); output not counted
def permute(nums):
    result, path = [], []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])            # copy: path is undone afterwards
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True                    # choose
            path.append(nums[i])
            backtrack()
            path.pop()                        # un-choose, so the next i starts clean
            used[i] = False

    backtrack()
    return result

// java
// LC 46 - Permutations
// IDEA: choose an unused number, recurse, un-choose; a full-length path is one permutation
// time = O(n * n!), space = O(n)
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));    // copy: path is undone afterwards
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) {
            continue;
        }
        used[i] = true;                       // choose
        path.add(nums[i]);
        backtrack(nums, used, path, result);
        path.remove(path.size() - 1);         // un-choose
        used[i] = false;
    }
}

# python
# LC 450 - Delete Node in a BST
# IDEA: return the new subtree root and let the parent reassign it; two children -> copy the successor in
# time = O(h), space = O(h)
def deleteNode(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = deleteNode(root.left, key)     # reassign: that subtree's root may change
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right                      # 0 or 1 child: lift the other side
        if not root.right:
            return root.left
        successor = root.right                     # 2 children: smallest node on the right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = deleteNode(root.right, successor.val)
    return root

// java
// LC 450 - Delete Node in a BST
// IDEA: return the new subtree root and let the parent reassign it; two children -> copy the successor in
// time = O(h), space = O(h)
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (key < root.val) {
        root.left = deleteNode(root.left, key);    // reassign: that subtree's root may change
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        TreeNode successor = root.right;
        while (successor.left != null) {
            successor = successor.left;
        }
        root.val = successor.val;
        root.right = deleteNode(root.right, successor.val);
    }
    return root;
}

# python
# LC 543 - Diameter of Binary Tree
# IDEA: post-order; return the height upward, record left + right (the path through this node) globally
# time = O(n), space = O(h)
def diameterOfBinaryTree(root):
    best = 0

    def height(node):
        nonlocal best
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        best = max(best, left + right)        # edges on the longest path that turns here
        return 1 + max(left, right)           # what the parent needs: one side only

    height(root)
    return best

// java
// LC 543 - Diameter of Binary Tree
// IDEA: post-order; return the height upward, record left + right (the path through this node) globally
// time = O(n), space = O(h)
private int best = 0;

public int diameterOfBinaryTree(TreeNode root) {
    best = 0;
    height(root);
    return best;
}

private int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = height(node.left);
    int right = height(node.right);
    best = Math.max(best, left + right);      // edges on the longest path that turns here
    return 1 + Math.max(left, right);         // what the parent needs: one side only
}

root = [1,2,3,4,5]          1
                           / \
                          2   3
                         / \
                        4   5
height(4) = 1, height(5) = 1     at 2: best = 1 + 1 = 2, return 2
height(3) = 1                    at 1: best = max(2, 2 + 1) = 3, return 3
answer 3   (the path 4-2-1-3 has 3 edges)

LC 979 trace — root = [0, 3, 0]        balance = val - 1 + left + right

        0                 dfs(left  3) -> 3 - 1 + 0 + 0 = +2   moves += 2   (2 coins go UP)
       / \                dfs(right 0) -> 0 - 1 + 0 + 0 = -1   moves += 1   (1 coin  goes DOWN)
      3   0               dfs(root  0) -> 0 - 1 + 2 + (-1) = 0            <- always 0 at root

  total moves = 2 + 1 = 3

# python
# LC 979 - Distribute Coins in Binary Tree
# IDEA: post-order DFS; each subtree returns its net balance, each edge costs |balance| moves
# time = O(n), space = O(h)   # h = tree height, worst O(n)
class Solution:
    def distributeCoins(self, root):
        self.moves = 0

        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)                 # net surplus/deficit of left subtree
            right = dfs(node.right)               # net surplus/deficit of right subtree
            balance = node.val - 1 + left + right # keep 1 coin, push the rest up
            self.moves += abs(balance)            # this subtree's edge to its parent
            return balance                        # signed, never abs()

        dfs(root)
        return self.moves

// java
// LC 979 - Distribute Coins in Binary Tree
// IDEA: post-order DFS; each subtree returns its net balance, each edge costs |balance| moves
// time = O(n), space = O(h)
private int moves = 0;

public int distributeCoins(TreeNode root) {
    moves = 0;
    dfs(root);
    return moves;
}

private int dfs(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = dfs(node.left);
    int right = dfs(node.right);
    int balance = node.val - 1 + left + right;  // keep 1 coin, push the rest up
    moves += Math.abs(balance);                 // this subtree's edge to its parent
    return balance;                             // signed, never Math.abs()
}

# python
# IDEA: sizes come children-first (reverse BFS order); removing x leaves its child subtrees + n - size(x)
# time = O(n), space = O(n)
# Iterative on purpose: n is up to 10^5 and a chain would overflow Python's recursion limit.
# LC 2049 - Count Nodes With the Highest Score
from collections import deque

def countHighestScoreNodes(parents):
    n = len(parents)
    children = [[] for _ in range(n)]
    for node in range(1, n):                 # parents[0] == -1: node 0 is the root
        children[parents[node]].append(node)

    order = []                               # BFS order from the root
    queue = deque([0])
    while queue:
        node = queue.popleft()
        order.append(node)
        queue.extend(children[node])

    size = [1] * n
    best_score = 0
    best_count = 0
    for node in reversed(order):             # every child is finished before its parent
        score = 1
        for child in children[node]:
            score *= size[child]             # each child's subtree is one component
            size[node] += size[child]
        above = n - size[node]               # everything outside this subtree
        if above > 0:                        # the root has nothing above it
            score *= above
        if score > best_score:
            best_score, best_count = score, 1
        elif score == best_score:
            best_count += 1
    return best_count

# python
# LC 1254 - Number of Closed Islands
# IDEA: pass 1 floods every island touching the border; pass 2 counts the islands left (0 = land here)
# time = O(m * n), space = O(m * n)
def closedIsland(grid):
    rows, cols = len(grid), len(grid[0])

    def flood(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 1:
            return
        grid[r][c] = 1                        # land -> water, which also marks it visited
        flood(r + 1, c)
        flood(r - 1, c)
        flood(r, c + 1)
        flood(r, c - 1)

    # pass 1: remove every island that touches the border
    for c in range(cols):
        flood(0, c)
        flood(rows - 1, c)
    for r in range(rows):
        flood(r, 0)
        flood(r, cols - 1)

    # pass 2: every island still standing is closed
    count = 0
    for r in range(1, rows - 1):
        for c in range(1, cols - 1):
            if grid[r][c] == 0:
                count += 1
                flood(r, c)
    return count

// java
// LC 1254 - Number of Closed Islands
// IDEA: pass 1 floods every island touching the border; pass 2 counts the islands left (0 = land here)
// time = O(m * n), space = O(m * n)
public int closedIsland(int[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    for (int c = 0; c < cols; c++) {          // pass 1: top and bottom borders
        flood(grid, 0, c);
        flood(grid, rows - 1, c);
    }
    for (int r = 0; r < rows; r++) {          // pass 1: left and right borders
        flood(grid, r, 0);
        flood(grid, r, cols - 1);
    }
    int count = 0;                            // pass 2: every island left is closed
    for (int r = 1; r < rows - 1; r++) {
        for (int c = 1; c < cols - 1; c++) {
            if (grid[r][c] == 0) {
                count++;
                flood(grid, r, c);
            }
        }
    }
    return count;
}

private void flood(int[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 1) {
        return;
    }
    grid[r][c] = 1;                           // land -> water, which also marks it visited
    flood(grid, r + 1, c);
    flood(grid, r - 1, c);
    flood(grid, r, c + 1);
    flood(grid, r, c - 1);
}

# python
# LC 694 - Number of Distinct Islands
# IDEA: record the move into each cell and a 'B' on the way back; equal shapes give equal strings
# time = O(m * n), space = O(m * n)
def numDistinctIslands(grid):
    rows, cols = len(grid), len(grid[0])
    shapes = set()

    def dfs(r, c, move, path):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return
        grid[r][c] = 0                        # mark visited
        path.append(move)
        dfs(r + 1, c, 'D', path)              # a FIXED order: down, up, right, left
        dfs(r - 1, c, 'U', path)
        dfs(r, c + 1, 'R', path)
        dfs(r, c - 1, 'L', path)
        path.append('B')                      # back marker: this cell's branch is finished

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                path = []
                dfs(r, c, 'S', path)          # 'S' = the start cell
                shapes.add(''.join(path))
    return len(shapes)

// java
// LC 694 - Number of Distinct Islands
// IDEA: record the move into each cell and a 'B' on the way back; equal shapes give equal strings
// time = O(m * n), space = O(m * n)
public int numDistinctIslands(int[][] grid) {
    Set<String> shapes = new HashSet<>();
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                StringBuilder path = new StringBuilder();
                dfs(grid, r, c, 'S', path);
                shapes.add(path.toString());
            }
        }
    }
    return shapes.size();
}

private void dfs(int[][] grid, int r, int c, char move, StringBuilder path) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 0;                           // mark visited
    path.append(move);
    dfs(grid, r + 1, c, 'D', path);           // a FIXED order: down, up, right, left
    dfs(grid, r - 1, c, 'U', path);
    dfs(grid, r, c + 1, 'R', path);
    dfs(grid, r, c - 1, 'L', path);
    path.append('B');                         // back marker
}

Shape A   1 1        Shape B   1 .
          1 .                  1 1

order D, U, R, L from the top-left cell
A: S, D to (1,0), back, R to (0,1), back, back  ->  "SDBRBB"
B: S, D to (1,0), R to (1,1), back, back, back  ->  "SDRBBB"
without the 'B's both are "SDR"

# python
# LC 1219 - Path with Maximum Gold
# IDEA: DFS from every gold cell; mark on entry, restore on exit; the guard at the top of the child
# time = O(k * 3^k), space = O(k)   k = number of gold cells (k <= 25)
class Solution:
    def getMaximumGold(self, grid):
        self.max_gold = 0
        rows, cols = len(grid), len(grid[0])
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] > 0:
                    self.dfs(grid, r, c, 0)            # start value = 0
        return self.max_gold

    def dfs(self, grid, r, c, cur_gold):
        rows, cols = len(grid), len(grid[0])
        # GUARD: off the grid, empty (0) or on the current path (-1) -> stop
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] <= 0:
            return
        cache = grid[r][c]
        cur_gold += cache                              # ACCUMULATE this cell
        self.max_gold = max(self.max_gold, cur_gold)   # UPDATE MAX on every cell entry
        grid[r][c] = -1                                # mark: on the current path
        self.dfs(grid, r + 1, c, cur_gold)             # the guard filters every direction
        self.dfs(grid, r - 1, c, cur_gold)
        self.dfs(grid, r, c + 1, cur_gold)
        self.dfs(grid, r, c - 1, cur_gold)
        grid[r][c] = cache                             # RESTORE: off the path again

// java
// LC 1219 - Path with Maximum Gold
// IDEA: DFS from every gold cell; mark on entry, restore on exit; the guard at the top of the child
// time = O(k * 3^k), space = O(k)
private int maxGold = 0;

public int getMaximumGold(int[][] grid) {
    maxGold = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] > 0) {
                dfs(grid, r, c, 0);
            }
        }
    }
    return maxGold;
}

private void dfs(int[][] grid, int r, int c, int curGold) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] <= 0) {
        return;                                        // off the grid, empty, or on the path
    }
    int cache = grid[r][c];
    curGold += cache;
    maxGold = Math.max(maxGold, curGold);
    grid[r][c] = -1;                                   // mark: on the current path
    dfs(grid, r + 1, c, curGold);
    dfs(grid, r - 1, c, curGold);
    dfs(grid, r, c + 1, curGold);
    dfs(grid, r, c - 1, curGold);
    grid[r][c] = cache;                                // restore: off the path again
}

# python
# LC 1219 - Path with Maximum Gold (V0-2)
# IDEA: guard BEFORE each recursive call, so no frame is spent on an invalid neighbour;
#       the launch loop's `if grid[y][x] > 0` validates the START cell
# time = O(k * 3^k), space = O(k)
class Solution:
    def getMaximumGold(self, grid):
        self.max_gold = 0
        L, W = len(grid), len(grid[0])
        for y in range(L):
            for x in range(W):
                if grid[y][x] > 0:
                    self.dfs(grid, x, y, grid[y][x])   # start value = the cell itself
        return self.max_gold

    def dfs(self, grid, x, y, cur_gold):
        L, W = len(grid), len(grid[0])
        self.max_gold = max(self.max_gold, cur_gold)   # (3) UPDATE MAX per cell entry — safe
        cache = grid[y][x]
        grid[y][x] = -1                                # mark visited
        moves = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        for dx, dy in moves:
            x_, y_ = x + dx, y + dy
            # (1) GUARD before recursing  +  (2) ACCUMULATE at the call site
            if 0 <= x_ < W and 0 <= y_ < L and grid[y_][x_] > 0:
                self.dfs(grid, x_, y_, cur_gold + grid[y_][x_])
        grid[y][x] = cache                             # BACKTRACK: restore

# python
# LC 1219 - Path with Maximum Gold (V0-3)
# IDEA: same as V0-2, but max_gold is updated INSIDE the loop (on next_gold), so the entry cell is
#       never scored by the DFS itself and the launch loop must SEED max_gold with grid[y][x]
# time = O(k * 3^k), space = O(k)
class Solution:
    def getMaximumGold(self, grid):
        self.max_gold = 0
        L, W = len(grid), len(grid[0])
        for y in range(L):
            for x in range(W):
                if grid[y][x] > 0:
                    self.max_gold = max(self.max_gold, grid[y][x])  # REQUIRED seed
                    self.dfs(grid, x, y, grid[y][x])
        return self.max_gold

    def dfs(self, grid, x, y, cur_gold):
        L, W = len(grid), len(grid[0])
        cache = grid[y][x]
        grid[y][x] = -1                                # mark visited (once per frame)
        moves = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        for dx, dy in moves:
            x_, y_ = x + dx, y + dy
            if 0 <= x_ < W and 0 <= y_ < L and grid[y_][x_] > 0:
                # mark/unmark is per cell entry, not per neighbour: do not touch grid[y][x] here
                next_gold = cur_gold + grid[y_][x_]
                self.max_gold = max(self.max_gold, next_gold)   # (3) UPDATE MAX in loop
                self.dfs(grid, x_, y_, next_gold)
        grid[y][x] = cache                             # BACKTRACK: restore

# python
# LC 399 - Evaluate Division
# IDEA: weighted graph a -> b (v) and b -> a (1/v); a DFS multiplies the weights along one path
# time = O(Q * (V + E)), space = O(V + E)
from collections import defaultdict

def calcEquation(equations, values, queries):
    graph = defaultdict(dict)
    for (a, b), value in zip(equations, values):
        graph[a][b] = value
        graph[b][a] = 1.0 / value               # the reverse edge, reciprocal weight

    def dfs(node, target, visited):
        if node == target:
            return 1.0
        visited.add(node)
        for nxt, weight in graph[node].items():
            if nxt not in visited:
                rest = dfs(nxt, target, visited)
                if rest != -1.0:
                    return weight * rest        # node/nxt * nxt/target = node/target
        return -1.0

    answers = []
    for x, y in queries:
        if x not in graph or y not in graph:
            answers.append(-1.0)                # an unknown variable, even for x / x
        else:
            answers.append(dfs(x, y, set()))    # a fresh visited set per query
    return answers

// java
// LC 399 - Evaluate Division
// IDEA: weighted graph a -> b (v) and b -> a (1/v); a DFS multiplies the weights along one path
// time = O(Q * (V + E)), space = O(V + E)
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    Map<String, Map<String, Double>> graph = new HashMap<>();
    for (int i = 0; i < equations.size(); i++) {
        String a = equations.get(i).get(0);
        String b = equations.get(i).get(1);
        graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, values[i]);
        graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / values[i]);
    }
    double[] answers = new double[queries.size()];
    for (int i = 0; i < queries.size(); i++) {
        String x = queries.get(i).get(0);
        String y = queries.get(i).get(1);
        if (!graph.containsKey(x) || !graph.containsKey(y)) {
            answers[i] = -1.0;                  // an unknown variable, even for x / x
        } else {
            answers[i] = dfs(graph, x, y, new HashSet<>());   // a fresh visited set per query
        }
    }
    return answers;
}

private double dfs(Map<String, Map<String, Double>> graph, String node, String target, Set<String> visited) {
    if (node.equals(target)) {
        return 1.0;
    }
    visited.add(node);
    for (Map.Entry<String, Double> edge : graph.get(node).entrySet()) {
        if (!visited.contains(edge.getKey())) {
            double rest = dfs(graph, edge.getKey(), target, visited);
            if (rest != -1.0) {
                return edge.getValue() * rest;  // node/next * next/target
            }
        }
    }
    return -1.0;
}

DFS Problem Analysis Flowchart:

1. Is it a tree/graph traversal problem?
   ├── YES → Check structure type
   │   ├── Tree? → Use Tree Templates (1, 3, 5, 6)
   │   │   ├── Need specific order? → Template 1 (Traversal)
   │   │   ├── Need paths? → Template 3 (Path Finding)
   │   │   ├── Need to modify? → Template 5 (Modification)
   │   │   └── Need subtree info? → Template 6 (Bottom-up)
   │   └── Graph? → Use Graph Template (2)
   │       ├── Has cycles? → Add visited set
   │       ├── Need all paths? → Track path
   │       └── Multi-source? → Start from all sources
   └── NO → Continue to 2

2. Is it a combinatorial problem?
   ├── YES → Use Backtracking Template (4)
   │   ├── Permutations? → Swap elements
   │   ├── Combinations? → Start index
   │   ├── Subsets? → Include/exclude
   │   └── Constraint satisfaction? → Check validity
   └── NO → Continue to 3

3. Does it require exploring all possibilities?
   ├── YES → Use DFS with appropriate state tracking
   │   ├── Grid problem? → 4-directional DFS
   │   ├── String problem? → Index-based DFS
   │   └── Decision tree? → Choice-based DFS
   └── NO → Consider different algorithm

4. Special considerations:
   ├── Need shortest path? → Consider BFS instead
   ├── Has optimal substructure? → Consider DP
   └── Need all solutions? → DFS with backtracking