while (!q.isEmpty()) { intsize= q.size(); minutes++; for (ints=0; s < size; s++) { int[] cur = q.poll(); for (int[] d : dirs) { intx= cur[0] + d[0], y = cur[1] + d[1]; if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1) continue; grid[x][y] = 2; fresh--; q.offer(newint[]{x, y}); } } }
return fresh == 0 ? minutes : -1; } }
⏱ Time and Space Complexity
Time Complexity: O(m × n), each cell is visited at most once.
Space Complexity: O(m × n) for the BFS queue.
✍️ Summary
Treat all rotten oranges as starting points.
Run BFS layer by layer to simulate time passing.
Return minutes when all fresh oranges are rotten, otherwise -1.
Given the root of a binary tree, return the maximum path sum of the tree.
A path is any sequence of nodes where each pair of adjacent nodes has an edge connecting them. A path does not need to pass through the root and cannot revisit a node. The path sum is the sum of node values along the path.
💬 Examples
Example 1
1 2 3
Input: root = [1,2,3] Output: 6 Explanation: The maximum path is 2 → 1 → 3.
Example 2
1 2 3
Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The maximum path is 15 → 20 → 7.
💡 Intuition
At each node, there are two different concepts:
Max Gain to Parent (what we can return upward): max(node.val, node.val + leftGain, node.val + rightGain)
This represents the best one-side path that can be extended by the parent.
Max Path Through Node (candidate for global answer): node.val + max(0, leftGain) + max(0, rightGain)
When a path goes through the current node and uses both sides (if beneficial).
Negative gains should be treated as 0 (i.e., discard them).
We do a postorder DFS to compute gains bottom-up while maintaining a global maximum.
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q.
The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).
💬 Example
Example 1
1 2 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.
Example 2
1 2 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself.
💡 Approach: Recursive DFS
We traverse the binary tree recursively:
If the current node is null, return null.
If the current node matches p or q, return it.
Recursively search left and right subtrees.
If both left and right return non-null, the current node is the LCA.
Otherwise, return the non-null child.
🔢 Java Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution {{ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {{ if (root == null || root == p || root == q) {{ return root; }}
Given the root of a binary tree, imagine you are standing on the right side of it. Return the values of the nodes you can see ordered from top to bottom.
while (!queue.isEmpty()) { intsize= queue.size(); for (inti=0; i < size; i++) { TreeNodenode= queue.poll(); if (i == size - 1) { // last node in this level result.add(node.val); } if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } } return result; } }
💡 Approach 2: DFS (Right-First Preorder)
We can also use DFS, always visiting right child first so the first node we encounter at each depth is the visible one.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public List<Integer> rightSideView(TreeNode root) { List<Integer> result = newArrayList<>(); dfs(root, 0, result); return result; }
while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); if (--k == 0) return curr.val; curr = curr.right; } return -1; // should not reach here if k is valid } }
💡 Approach 2: Recursive Inorder Traversal
We can also use recursion with a counter to track when we reach the k-th element.