leetcode DFS+BFS+DSU question brushing summary 2
1-symmetric binary tree
Title Link: Link here!!!
Idea 1: iterative method
For a binary tree, the left and right subtrees enter the queue respectively. If the left and right subtrees are empty, the traversal ends. If only one of the left and right subtrees is empty, or the root nodes of the left and right subtrees are different, false is returned. Otherwise, the queue is entered in the order of the left subtree of the left node, the right subtree of the right node, the right subtree of the left node and the left subtree of the right node.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true ;
}
Queue<TreeNode> queue = new LinkedList<>() ;
queue.add(root.left) ;
queue.add(root.right) ;
while(!queue.isEmpty()){
TreeNode node1 = queue.poll() ;
TreeNode node2 = queue.poll() ;
if(node1 == null && node2 == null){
continue ;
}
if(node1==null || node2==null || node1.val != node2.val){
return false ;
}
queue.add(node1.left) ;
queue.add(node2.right) ;
queue.add(node1.right) ;
queue.add(node2.left) ;
}
return true ;
}
}
Train of thought 2: recursive method
The method is the same as that of train of thought 1, but the queue is not used. It is compared directly recursively.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true ;
}
return f(root.left, root.right) ;
}
public boolean f(TreeNode node1, TreeNode node2){
if(node1==null && node2==null){
return true ;
}
if(node1==null || node2==null || node1.val != node2.val){
return false ;
}
return f(node1.left,node2.right) && f(node1.right,node2.left) ;
}
}
Hierarchical traversal of 2-binary tree
Title Link: Title Link stamp here!!!
Idea 1: bfs
With the help of queue, first let the root node join the queue. As long as the queue is not empty, calculate the size of the queue, put the root node of each layer into the set each time, and join the left and right subtrees at the same time.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null){
return new ArrayList<>() ;
}
List<List<Integer>> ans = new ArrayList<>() ;
Queue<TreeNode> queue = new LinkedList<>() ;
queue.add(root) ;
while(!queue.isEmpty()){
int size = queue.size() ;
List<Integer> list = new ArrayList<>() ;
while(size>0){
TreeNode node = queue.poll() ;
list.add(node.val) ;
if(node.left != null){
queue.add(node.left) ;
}
if(node.right != null){
queue.add(node.right) ;
}
size -- ;
}
ans.add(list) ;
}
return ans ;
}
}
Zigzag traversal of 3-binary tree
Title Link: Title Link stamp here!!!
Idea: bfs + flip
The idea is the same as that of hierarchy traversal, except that for the elements of even layers, after they are stored in the collection, the odd elements can be flipped.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if(root==null){
return new ArrayList<>() ;
}
List<List<Integer>> ans = new ArrayList<>() ;
Queue<TreeNode> queue = new LinkedList<>() ;
queue.add(root) ;
while(!queue.isEmpty()){
int size = queue.size() ;
boolean level = true ;
List<Integer> list = new ArrayList<>() ;
while(size>0){
TreeNode node = queue.poll() ;
list.add(node.val) ;
if(node.left != null){
queue.add(node.left) ;
}
if(node.right != null){
queue.add(node.right) ;
}
size -- ;
}
if(ans.size()%2!=0){
Collections.reverse(list) ;
}
ans.add(list) ;
}
return ans ;
}
}
Maximum depth of 4-binary tree
Title Link: Title Link stamp here!!!
Idea 1: recursive method
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0 ;
}
return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1 ;
}
}
Train of thought 2: bfs
The queue is used for hierarchical traversal, and the height of the binary tree without traversing one layer is increased by 1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0 ;
}
int height = 0 ;
Queue<TreeNode> queue = new LinkedList<>() ;
queue.add(root) ;
while(!queue.isEmpty()){
int size = queue.size();
height ++ ;
for(int i=0; i<size; i++){
TreeNode node = queue.poll() ;
if(node.left != null){
queue.add(node.left) ;
}
if(node.right != null){
queue.add(node.right) ;
}
}
}
return height ;
}
}
Sequence traversal of 5-binary Tree II
Title Link: Title Link stamp here!!!
Idea: bfs
bfs performs hierarchical traversal, and the traversal results of each layer are inserted into the head of the result set.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
if(root==null){
return new ArrayList<>() ;
}
LinkedList<List<Integer>> ans = new LinkedList<>() ;
Queue<TreeNode> queue = new LinkedList<>() ;
queue.add(root) ;
while(!queue.isEmpty()){
int size = queue.size() ;
List<Integer> temp = new LinkedList<>() ;
for(int i=0; i<size; i++){
TreeNode node = queue.poll() ;
temp.add(node.val) ;
if(node.left != null){
queue.add(node.left) ;
}
if(node.right != null){
queue.add(node.right) ;
}
}
ans.addFirst(temp) ;
}
return ans ;
}
}
Minimum depth of 6-binary tree
Title Link: Title Link stamp here!!!
Idea 1: dfs method
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root==null){
return 0 ;
}
if(root.left==null && root.right != null){ //The left subtree of the root node is empty. Only the right subtree needs to be considered
return minDepth(root.right) + 1 ;
}
if(root.right==null && root.left!=null){//The right subtree of the root node is empty, and only the left subtree needs to be considered
return minDepth(root.left) + 1 ;
}
return Math.min(minDepth(root.left),minDepth(root.right)) + 1 ;
}
}
Train of thought 2: bfs
Enter the root node into the queue. If the queue is not empty, traverse the hierarchy in turn. If the left and right subtrees of a certain layer are empty, end the traversal, otherwise continue the traversal.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root==null){
return 0 ;
}
Queue<TreeNode> queue = new LinkedList<>() ;
queue.add(root) ;
int height = 0 ;
while(!queue.isEmpty()){
int size = queue.size() ;
height ++ ;
for(int i=0; i<size; i++){
TreeNode node = queue.poll() ;
if(node.left==null && node.right==null){
return height ;
}
if(node.left!=null){
queue.add(node.left) ;
}
if(node.right!=null){
queue.add(node.right) ;
}
}
}
return height ;
}
}
7-minimum height tree
Title Link: Title Link stamp here!!!
Idea: topological sorting + bfs
Starting from the edge, we first find all nodes with degree 1, then put all nodes with degree 1 into the queue, and then constantly bfs. Finally, we find the nodes close to the middle on both sides at the same time. Then the middle node is equivalent to halving the whole distance, so it is of course the point with the smallest distance on both sides, That is, to the nearest node of other leaf nodes.
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> ans = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>() ;
List<List<Integer>> adj = new ArrayList<>() ;
if(n==1){
ans.add(0) ;
return ans ;
}
int [] degree = new int [n] ; //Record out degree
for(int i=0; i<n; i++){
adj.add(new ArrayList<>()) ;
}
for(int []edge : edges){
degree[edge[0]] ++ ;
degree[edge[1]] ++ ;
adj.get(edge[0]).add(edge[1]) ;
adj.get(edge[1]).add(edge[0]) ;
}
for(int i=0; i<n; i++){
if(degree[i]==1){
queue.add(i) ;
}
}
while(!queue.isEmpty()){
int size = queue.size() ;
ans = new ArrayList<>() ;
for(int i=0; i<size; i++){
int x = queue.poll() ;
ans.add(x) ;
for(int y : adj.get(x)){
degree[y] -- ;
if(degree[y]==1){
queue.add(y) ;
}
}
}
}
return ans ;
}
}
8-flip binary tree
Title Link: Title Link stamp here!!!
Idea: recursively flip the left and right subtrees.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null){
return null ;
}
TreeNode left = invertTree(root.left) ;
TreeNode right = invertTree(root.right) ;
root.left = right ;
root.right = left ;
return root ;
}
}
9 - detection ring in two-dimensional grid diagram
Title Link: Title Link stamp here!!!
Idea: dfs
Use dfs to detect whether there is a ring
The condition of having a ring is to search the coordinates accessed by the dfs in the search process.
Define a two-dimensional array record and accessed coordinates.
Consider not searching the opposite direction of the direction according to the direction searched by the previous layer added in the search process.
In this case, if the visited node is found, it indicates that there is a ring, and if there is a ring, it will be returned directly.
class Solution {
boolean flag = false ;
boolean [][] vis;
public boolean containsCycle(char[][] grid) {
//For dfs search, you cannot move to the last place in one step. If you finally return to the place you visited before, there will be a ring
int m = grid.length ;
int n = grid[0].length ;
vis = new boolean[m][n] ;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(!vis[i][j]){
dfs(grid,i,j,grid[i][j],'L') ;
if(flag){
return true ;
}
}
}
}
return false ;
}
public void dfs(char [][] grid, int x, int y, char target, char c){
if(x<0 || y<0 || x>=grid.length || y>=grid[0].length || grid[x][y]!=target){
return ;
}
if(vis[x][y]){
flag = true ;
return ;
}
vis[x][y] = true ;
if(c!='L'){
dfs(grid,x,y-1,target,'R') ;
}
if(c!='R'){
dfs(grid,x,y+1,target,'L') ;
}
if(c!='U'){
dfs(grid,x-1,y,target,'D') ;
}
if(c!='D'){
dfs(grid,x+1,y,target,'U') ;
}
}
}
10 - inter node path
Title Link: Title Link stamp here!!!
Idea 1: adjacency table + dfs
Change the two-dimensional array into an adjacency table, that is, a directed acyclic graph. Search the graph from the starting point. If the target point is searched, it indicates that there is a path from start to target.
class Solution {
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
//dfs
List<List<Integer>> edges = new ArrayList<>() ;
for(int i=0; i<n; i++){
edges.add(new ArrayList<>()) ;
}
for(int [] g : graph){
edges.get(g[0]).add(g[1]) ;
}
return dfs(edges,start,target) ;
}
public boolean dfs(List<List<Integer>> edges, int start, int target){
if(start==target){
return true ;
}
for(int neighbors : edges.get(start)){
if(dfs(edges,neighbors,target)){
return true ;
}
}
return false ;
}
}
Idea 2: adjacency table + bfs
The adjacency table is established according to the graph array, and the adjacency table is traversed in breadth first. If the target is found, it returns true.
class Solution {
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
//bfs
List<List<Integer>> edges = new ArrayList<>() ;
for(int i=0; i<n; i++){
edges.add(new ArrayList<>()) ;
}
for(int [] g : graph){
edges.get(g[0]).add(g[1]) ;
}
Queue<Integer> queue = new LinkedList<>() ;
queue.add(start) ;
while(!queue.isEmpty()){
int x = queue.poll() ;
if(x==target){
return true ;
}
for(int neighbors : edges.get(x)){
if(neighbors==target){
return true ;
}
queue.add(neighbors) ;
}
}
return false ;
}
}
11 bipartite graph
Title Link: Title Link stamp here!!!
Idea 1: dfs + staining
We use graph search algorithm to traverse the whole connected domain from any vertex of each connected domain. In the process of traversal, we dye the vertices with two different colors, and the adjacent vertices are dyed in the opposite color. In this process, if it is found that the adjacent vertices are dyed with the same color, it indicates that it is not a bipartite graph; On the contrary, if all connected domains are dyed successfully, it shows that it is a bipartite graph.
class Solution {
int [] vis ;
public boolean isBipartite(int[][] graph) {
//dfs + staining
vis = new int [graph.length] ;
for(int i=0; i<graph.length; i++){
if(vis[i]==0 && !dfs(graph,i,vis,1)){
return false ;
}
}
return true ;
}
public boolean dfs(int [][] graph, int x, int [] vis, int color){
if(vis[x] != 0){
return vis[x]==color ;
}
vis[x] = color ;
for(int y : graph[x]){
if(!dfs(graph,y,vis,-color)){
return false ;
}
}
return true ;
}
}
Idea 2: bfs + staining
class Solution {
int [] vis ;
public boolean isBipartite(int[][] graph) {
//dfs + staining
vis = new int [graph.length] ;
Queue<Integer> queue = new LinkedList<>() ;
for(int i=0; i<graph.length; i++){
if(vis[i] != 0){
continue ;
}
queue.add(i) ;
vis[i] = 1 ;
while(!queue.isEmpty()){
int x = queue.poll() ;
for(int y : graph[x]){
if(vis[x]==vis[y]){
return false ;
}
if(vis[y]==0){
vis[y] = - vis[x] ;
queue.add(y) ;
}
}
}
}
return true ;
}
}
12 split palindrome substring
Title Link: Title Link stamp here!!!
Idea: memorizing dfs + backtracking
Assuming that we currently search for the second character of the string, and all characters at position s[0... i − 1] have been divided into several palindrome strings, and the segmentation results have been put into the answer array temp, then we need to enumerate the right bound j of the next palindrome string so that s[i... j] is a palindrome string.
Therefore, we can start with i and enumerate j from small to large. For the J value of the current enumeration, we use the double pointer method to judge whether s[i... J] is a palindrome string: if s[i... J] is a palindrome string, it will be added to the answer array temp, and j+1 will be used as the new i for the next layer of search, and s[i... J] will be removed from temp during future backtracking.
If we have searched the last character of the string, we have found a segmentation method that meets the requirements.
class Solution {
String [][] ans ;
List<List<String>> res = new ArrayList<>() ;
List<String> temp = new ArrayList<>() ;
int [][] f ;
public String[][] partition(String s) {
//Backtracking + memory search
f = new int [s.length()][s.length()] ;
dfs(0,s) ;
ans = new String[res.size()][] ;
for(int i=0; i<res.size(); i++){
ans[i] = new String[res.get(i).size()] ;
for(int j=0; j<res.get(i).size(); j++){
ans[i][j] = res.get(i).get(j) ;
}
}
return ans ;
}
public void dfs(int i, String s){
if(i==s.length()){
res.add(new ArrayList<>(temp)) ;
return ;
}
for(int j=i; j<s.length(); j++){
if(isPalindrome(s,i,j)==1){
temp.add(s.substring(i,j+1)) ;
dfs(j+1,s) ;
temp.remove(temp.size()-1) ;
}
}
}
public int isPalindrome(String s, int i, int j){
if(f[i][j] != 0){
return f[i][j] ;
}
if(i>=j){
f[i][j] = 1;
}else if(s.charAt(i) == s.charAt(j)){
f[i][j] = isPalindrome(s,i+1,j-1) ;
}else{
f[i][j] = -1;
}
return f[i][j] ;
}
}
13 depth of binary tree
Title Link: Title Link stamp here!!!
Idea 1: direct recursion
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0 ;
}
return Math.max(maxDepth(root.left),maxDepth(root.right))+1 ;
}
}
Idea 2: bfs traverses the hierarchy and records the depth of the tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0 ;
}
Queue<TreeNode> queue = new LinkedList<>() ;
int depth = 0 ;
queue.add(root) ;
while(!queue.isEmpty()){
int size = queue.size() ;
for(int i=0; i<size; i++){
TreeNode node = queue.poll() ;
if(node.left!=null){
queue.add(node.left) ;
}
if(node.right!=null){
queue.add(node.right) ;
}
}
depth ++ ;
}
return depth ;
}
}
14 - count the number of good nodes in the binary tree
Title Link: Title Link stamp here!!!
Idea: dfs searches the left and right subtrees. If it is larger than the current value, ans will add 1 and update the maximum value at the same time.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int ans = 0 ;
public int goodNodes(TreeNode root) {
dfs(root,Integer.MIN_VALUE) ;
return ans ;
}
public void dfs(TreeNode root, int max){
if(root==null){
return ;
}
if(root.val>=max){
ans ++ ;
}
dfs(root.left,Math.max(max,root.val)) ;
dfs(root.right,Math.max(max,root.val)) ;
}
}
15 - sum of left leaves
Title Link: Title Link stamp here!!!
Idea: search the left and right subtrees. If the left subtree of the current node is not empty and the left and right subtrees of the left subtree are empty, the current node is the left leaf node, which is accumulated.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int ans = 0 ;
public int sumOfLeftLeaves(TreeNode root) {
dfs(root) ;
return ans ;
}
public void dfs(TreeNode root){
if(root==null){
return ;
}
if(root.left != null && root.left.left==null && root.left.right==null){
ans += root.left.val ;
}
dfs(root.left) ;
dfs(root.right) ;
}
}
**
With you, the Star River is hot. Struggle, boy!!!
**