Depth-First-Search

LeetCode 2385 note: turn the tree into an undirected graph and BFS from start; the number of levels minus one is the answer

LeetCode 834 note: rerooting DP: compute subtree sizes and ans[0] with root 0, then push ans[child] = ans[parent] - size + (n - size) to every node

LeetCode 2858 note: rerooting DP: count the reversals needed with root 0, then moving the root to a child adds 1 if that edge pointed down and subtracts 1 if it pointed up

LeetCode 968 note: post-order greedy with three states per node: has a camera, covered, not covered; place a camera only when a child is uncovered, and add one if the root is left uncovered

LeetCode 863 note: turn the tree into an undirected graph (adding edges to parents), then BFS k steps from target

LeetCode 437 note: prefix sums on a tree with a hash map: look up prefix - target before adding the current prefix, and undo it when leaving the node

LeetCode 652 note: encode every subtree in post-order and report it on its second occurrence; string keys are O(n^2) worst case, (val, left id, right id) ids make it O(n)

LeetCode 99 note: find the inversions in the in-order sequence: the earlier node of the first inversion and the later node of the last one were swapped

LeetCode 449 note: for a BST, pre-order without null markers is enough; deserialize recursively with bounds in O(n)

LeetCode 297 note: pre-order with null markers identifies the tree uniquely; deserialize by consuming tokens from an iterator

LeetCode 687 note: DFS returns the longest same-value downward chain in edges, and each node updates the answer with left + right

LeetCode 515 note: BFS level order, taking the maximum of each level; start from -inf