Depth-First Search

ProblemGiven a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors. 12345class Node { public int val; public List<Node> neighbors;} Test case format: For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the te ...

ProblemThere are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network. You are given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connecte ...

ProblemGiven the root of a binary tree, flatten the tree into a “linked list”: The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The “linked list” should be in the same order as a pre-order traversal of the binary tree. Example 1: !https://assets.leetcode.com/uploads/2021/01/14/flaten.jpg 123Input: root = [1,2,5,3,4,null,6]Output: [1,null,2,null,3,null,4,null,5,null,6] Example 2: 1 ...

ProblemGiven the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Example 1: !https://assets.leetcode.com/uploads/2021/02/19/symtree1.jpg 123Input: root = [1,2,2,3,4,4,3]Output: true Example 2: !https://assets.leetcode.com/uploads/2021/02/19/symtree2.jpg 123Input: root = [1,2,2,null,3,null,3]Output: false Constraints: The number of nodes in the tree is in the range [1, 1000]. 100 <= Node.val <= 100 Follow up: Could you solve it both r ...

ProblemGiven the root of a binary tree, return its maximum depth. A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Example 1: !https://assets.leetcode.com/uploads/2020/11/26/tmp-tree.jpg 123Input: root = [3,9,20,null,null,15,7]Output: 3 Example 2: 123Input: root = [1,null,2]Output: 2 Constraints: The number of nodes in the tree is in the range [0, 104]. 100 <= Node.val <= 100 Solve解11234567891011121314151617 ...

ProblemIn this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph. Return an edge that can be removed so that ...

ProblemGiven an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: 12345678Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"] ...

ProblemA path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node’s values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path. Example 1: !https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg 1234Input: root = [1,2,3]Output: 6 ...

ProblemThere are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key. When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms. Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true  ...

ProblemThe thief has found himself a new place for his thievery again. There is only one entrance to this area, called root. Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night. Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police ...