Breadth-First-Search

LeetCode 117 note: connect next pointers level by level with BFS; for a non-perfect tree, looking only at the neighbour’s children breaks the chain

LeetCode 116 note: in a perfect binary tree, walk each level through the next pointers already set on the level above: left.next = right and right.next = next.left, with O(1) extra space

LeetCode 107 note: a normal level-order traversal reversed at the end gives bottom-up order

LeetCode 103 note: a normal level-order traversal with every odd level reversed gives the zigzag

LeetCode 1379 note: walk both trees in lockstep; when the original reaches target, the clone’s node at the same position is the answer, comparing node identity

LeetCode 695 note: DFS each unvisited 1 to measure its island and keep the maximum; cells are the integer 1, not a string

LeetCode 417 note: walk inward from each ocean’s shore to cells no lower than the current one; cells reached from both oceans are the answer

LeetCode 133 note: during DFS map each old node to its copy and return the existing copy when revisited, avoiding infinite recursion; an empty graph returns None

LeetCode 199 note: in a level-order traversal, each level’s rightmost node is what you see from the right

LeetCode 1448 note: pass the path maximum down during DFS; a node is good when its value is at least that maximum

LeetCode 102 note: BFS one whole level at a time, building the next level from the current one; an empty tree returns an empty list

LeetCode 993 note: cousins share a depth but not a parent; record x’s and y’s depth and parent during DFS and compare