Han Zhu's Study Notes

Given a binary tree, find the leftmost value in the last row of the tree. Example 1: Input: 2 / \ 1 3 Output: 1 Example 2:  Input: 1 / \ 2 3 / / \ 4 5 6 / 7 Output: 7 Note:  You may assume the tree (i.e., the given root node) is not  NULL . Thought process: BFS. Level order traversal. Use a variable to keep track of the first node of each level. Solution 1 (BFS): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int findBottomLeftValue(TreeNode root) { Queue < TreeNode > queue = new LinkedList <> (); queue.offer(root); TreeNode bl = null; while ( ! queue.isEmpty()) {...

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree  [1,2,2,3,4,4,3]  is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following  [1,2,2,null,3,null,3]  is not: 1 / \ 2 2 \ \ 3 3 Note: Bonus points if you could solve it both recursively and iteratively. Thought process: Recursive: traverse the tree and check if left matches right. Iterative: BFS. Solution 1 (Recursive): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric ( TreeNode root ) { if ( root == null ) { return true ; } return isSymmetric ( root . left , r...

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note: The input string may contain letters other than the parentheses  (  and  ) . Examples: "()())()" -> ["()()()", "(())()"] "(a)())()" -> ["(a)()()", "(a())()"] ")(" -> [""] Thought process: BFS: Graph definition: Vertex: a candidate string. Edge: two strings s1 and s2 have an edge if s1 equals s2 with one parenthesis deleted. Put string into a queue. For the current size of the queue, poll a string from the queue. Iterate through the string. For each character, remove it, and check if the parentheses are valid. If so, iterate over current level and return the result. If not, offer the new string to the queue. Solution 1 (BFS): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 ...

You are given a  m x n  2D grid initialized with these three possible values. -1  - A wall or an obstacle. 0  - A gate. INF  - Infinity means an empty room. We use the value  2 31  - 1 = 2147483647  to represent  INF  as you may assume that the distance to a gate is less than  2147483647 . Fill each empty room with the distance to its  nearest  gate. If it is impossible to reach a gate, it should be filled with  INF . For example, given the 2D grid: INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF After running your function, the 2D grid should be: 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4 Thought process: Iterate through the grid. Add gates' coordinates to queue. BFS from gates and expand through all rooms. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public class Solution { private final ...

Given  n  nodes labeled from  0  to  n - 1  and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given  n = 5  and  edges = [[0, 1], [0, 2], [0, 3], [1, 4]] , return  true . Given  n = 5  and  edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] , return  false . Note : you can assume that no duplicate edges will appear in  edges . Since all edges are undirected,  [0, 1]  is the same as  [1, 0] and thus will not appear together in  edges . Thought process: A tree is a graph that doesn't have a cycle. BFS. When a node is polled from queue, iterate through its neighbors. If any of them is visited but not the node's parent, there is a cycle. If there are no edges, then the graph is a tree only if it has only one node. Build graph. Use a map of int -> list of int. Iterate through the edg...

There are a total of  n  courses you have to take, labeled from  0  to  n - 1 . Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:  [0,1] Given the total number of courses and a list of prerequisite  pairs , return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array. For example: 2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is  [0,1] 4, [[1,0],[2,0],[3,1],[3,2]] There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is  [0,1,2,3] . Another correct ordering is [0,2,1,3] . Note:...