DFS Flashcards
- Evaluate Boolean Binary Tree
Easy
895
26
company
Google
You are given the root of a full binary tree with the following properties:
Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True.
Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.
The evaluation of a node is as follows:
If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
Otherwise, evaluate the node’s two children and apply the boolean operation of its value with the children’s evaluations.
Return the boolean result of evaluating the root node.
A full binary tree is a binary tree where each node has either 0 or 2 children.
A leaf node is a node that has zero children.
class Solution {
public boolean evaluateTree(TreeNode root) {
return dfs(root);
}
boolean dfs(TreeNode root){
boolean left = false;
boolean right = false;
if(root==null){
return true;
}
if(root.left== null && root.right == null && root.val == 1){
return true;
}
if(root.left== null && root.right == null && root.val == 0){
return false;
}
if(root.left!=null && root.right!=null && root.val == 2){
return dfs(root.left)|| dfs(root.right);
}
if(root.left!=null && root.right!=null && root.val == 3){
return dfs(root.left) && dfs(root.right);
}
return false;
} }
- Number of Islands
Medium
Given 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:
Input: grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
Output: 1
Example 2:
Input: grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
Output: 3
class Solution {
int count = 0;
public int numIslands(char[][] grid) {
for(int i =0;i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
if(grid[i][j]==’1’){
count++;
dfs(i,j,grid);
}
}
}
return count;
}
void dfs(int i , int j , char[][] grid){
if(i<0 || j<0 || i>=grid.length || j>=grid[0].length || grid[i][j]==’0’){
return;
}
grid[i][j]=’0’;
dfs(i+1, j,grid);
dfs(i-1,j,grid);
dfs(i,j+1,grid);
dfs(i,j-1,grid);
}
}
- Construct String from Binary Tree
Easy
Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Input: root = [1,2,3,4]
Output: “1(2(4))(3)”
Explanation: Originally, it needs to be “1(2(4)())(3()())”, but you need to omit all the unnecessary empty parenthesis pairs. And it will be “1(2(4))(3)”
/**
* 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 String tree2str(TreeNode root) {
if (root == null) {
return “”;
}
// Step 1: Start with an empty result string
StringBuilder result = new StringBuilder();
// Step 2: Perform preorder traversal
preorderTraversal(root, result);
// Step 3: Return the final result string
return result.toString();
}
private void preorderTraversal(TreeNode node, StringBuilder result) {
if (node == null) {
return;
}
// Step 4: Append the current node’s value to the result
result.append(node.val);
// Step 5: Check if the current node has a left child or a right child
if (node.left != null || node.right != null) {
// Step 6: If there is a left child, add empty parentheses for it
result.append(“(“);
preorderTraversal(node.left, result);
result.append(“)”);
}
// Step 7: If there is a right child, process it similarly
if (node.right != null) {
result.append(“(“);
preorderTraversal(node.right, result);
result.append(“)”);
}
// Step 8: The recursion will handle all the child nodes
}
}
- Lowest Common Ancestor of a Binary Tree
Medium
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
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.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
if(root.val == p.val ||root.val ==q.val){
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left!=null && right!=null){
return root;
}
if(left!=null){
return left;
}
else{
return right;
}
} }
- Max Area of Island
Medium
You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
Example 1:
Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
class Solution {
int area = 0;
int max_area = 0;
public int maxAreaOfIsland(int[][] grid) {
for(int i =0;i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
if(grid[i][j]==1){
area = 0;
dfs(grid, i, j);
if(area>max_area){
max_area=area;
}
}
}
}
return max_area;
}
public void dfs(int[][] grid, int i, int j){
if(i<0 ||j<0 ||i>=grid.length|| j>=grid[0].length || grid[i][j]==0){
return ;
}
grid[i][j]=0;
area++;
dfs(grid, i+1,j);
dfs(grid, i-1,j);
dfs(grid, i,j+1);
dfs(grid, i,j-1);
}
}
Console
- Minesweeper
Medium
Let’s play the minesweeper game (Wikipedia, online game)!
You are given an m x n char matrix board representing the game board where:
‘M’ represents an unrevealed mine,
‘E’ represents an unrevealed empty square,
‘B’ represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),
digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and
‘X’ represents a revealed mine.
You are also given an integer array click where click = [clickr, clickc] represents the next click position among all the unrevealed squares (‘M’ or ‘E’).
Return the board after revealing this position according to the following rules:
If a mine ‘M’ is revealed, then the game is over. You should change it to ‘X’.
If an empty square ‘E’ with no adjacent mines is revealed, then change it to a revealed blank ‘B’ and all of its adjacent unrevealed squares should be revealed recursively.
class Solution {
char[][] output;
boolean[][] visited;
public char[][] updateBoard(char[][] board, int[] click) {
output = board;
int x = click[0];
int y = click[1];
if(board[x][y]=='M'){
board[x][y]='X';
return board;
}
visited = new boolean[board.length][board[0].length];
dfs(x, y , visited);
for(int i=0;i<board.length;i++){
for(int j =0;j<board[0].length;j++){
System.out.println(output[i][j]);
}
}
return output;
}
public void dfs(int x, int y , boolean[][]visited){
if(x<0 ||y<0 || x>=output.length || y>=output[0].length||visited[x][y] ){
return ;
}
visited[x][y]=true;
if(output[x][y] == 'M') {
return;
}
int minesCount = minesCount(x, y);
if(minesCount>0){
output[x][y]=(char)(minesCount + '0');;
}
else{
output[x][y]='B';
}
if(output[x][y]!='M' && output[x][y]!='B' && output[x][y]!='X' && output[x][y]!='E')
return ;
dfs(x+1, y, visited);
dfs(x-1, y, visited);
dfs(x, y+1, visited);
dfs(x, y-1, visited);
dfs(x+1, y+1, visited);
dfs(x-1, y-1, visited);
dfs(x+1, y-1, visited);
dfs(x-1, y+1, visited);
} private int minesCount(int x, int y){
int count = 0;
for(int i =-1;i<2;i++){
for(int j=-1;j<2;j++){
if(i==0 && j==0){
continue;
}
int r = x+i;
int c = y+j;
if (r < 0 || r >= output.length || c < 0 || c < 0 || c >= output[0].length) continue;
if(output[r][c]=='M'){
count++;
}
}
}
return count; }
}
- The Maze
Medium
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball’s start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.
You may assume that the borders of the maze are all walls (see examples).
Example 1:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
Example 2:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: false
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.
Example 3:
Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: false
Constraints:
m == maze.length
n == maze[i].length
1 <= m, n <= 100
maze[i][j] is 0 or 1.
start.length == 2
destination.length == 2
0 <= startrow, destinationrow <= m
0 <= startcol, destinationcol <= n
Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
The maze contains at least 2 empty spaces.
class Solution {
int[] dirX = {0, 1, 0, -1};
int[] dirY = {-1, 0, 1, 0};
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
boolean[][] visit = new boolean[m][n];
boolean[][] visited = new boolean[m][n];
return dfs( m, n ,maze,start,destination,visited);
}
public boolean dfs(int m,int n, int [][]maze, int[] curr, int [] destination,boolean [][] visited){
if (visited[curr[0]][curr[1]]) {
return false;
}
if(curr[0]==destination[0] && curr[1]==destination[1]){
return true;
}
visited[curr[0]][curr[1]] = true;
for(int i =0;i<4;i++){
int curr_x = curr[0];
int curr_y = curr[1];
while(curr_x >= 0 && curr_y>=0 && curr_x < m && curr_y < n && maze[curr_x][curr_y]==0){
curr_x =curr_x+dirX[i];
curr_y = curr_y+dirY[i];
}
if (dfs(m, n, maze, new int[]{curr_x - dirX[i], curr_y - dirY[i]}, destination,visited)) {
return true;
}
}
return false;
}
}
- Island Perimeter
Solved
Easy
Topics
Companies
You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn’t have “lakes”, meaning the water inside isn’t connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.
Example 1:
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.
class Solution {
public int islandPerimeter(int[][] grid) { if (grid == null) return 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
return getPerimeter(grid, i, j);
}
}
}
return 0;
}
public int getPerimeter(int[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length||grid[i][j] == 0) {
return 1;
}
if (grid[i][j] == -1)
return 0;
int count = 0;
grid[i][j] = -1;
count += getPerimeter(grid, i - 1, j);
count += getPerimeter(grid, i, j - 1);
count += getPerimeter(grid, i, j + 1);
count += getPerimeter(grid, i + 1, j);
return count;
} }
- N-ary Tree Preorder Traversal
Solved
Easy
Topics
Companies
Given the root of an n-ary tree, return the preorder traversal of its nodes’ values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;</Node>
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
} }; */
class Solution {
List<Integer> li = new ArrayList<>();</Integer>
public List<Integer> preorder(Node root) {
dfs(root);
return li;
}
void dfs(Node root) {
if (root == null) {
return;
}
li.add(root.val);
List<Node> child = root.children;
for (int i = 0; i < child.size(); i++) {
dfs(child.get(i));
}
} }
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 –> 2): The sum is 3.
(1 –> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.
Example 3:
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.
/**
* 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 hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return dfs(root, targetSum-root.val) ;
}
public boolean dfs(TreeNode root, int targetSum){
boolean left = false;
boolean right = false;
if(root==null){
return false;
}
if(root.left==null && root.right == null && targetSum==0){
return true;
}
if(root.left!=null){
left = dfs(root.left, targetSum-root.left.val);
}
if(root.right !=null){
right = dfs(root.right, targetSum-root.right.val);
}
return left||right;
}
}
- Invert Binary Tree
Solved
Easy
Topics
Companies
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,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 TreeNode invertTree(TreeNode root) {
TreeNode right=null;
TreeNode left =null;
if(root==null){
return root;
}
if(root.left!=null)
right = invertTree(root.left);
if(root.right!=null)
left = invertTree(root.right);
root.left = left;
root.right = right;
return root;
} }
- Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2:
Input: root = []
Output: []
/**
* 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 {
List<Integer> output = new ArrayList<>();</Integer>
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return output;
}
dfs(root);
return output;
}
public void dfs(TreeNode root) {
if (root == null)
return;
dfs(root.left);
output.add(root.val);
dfs(root.right);
} }
- Sum of Left Leaves
Solved
Easy
Topics
Companies
Given the root of a binary tree, return the sum of all left leaves.
A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.
class Solution {
int sum = 0;
public int sumOfLeftLeaves(TreeNode root) {
if(root==null){
return 0;
}
dfs(root,false);
return sum;
}
public void dfs(TreeNode root, boolean isLeft){
if(root==null){
return ;
}
if(root.left==null && root.right==null && isLeft){
sum = sum+root.val;
}
if(root.left!=null){
dfs(root.left,true);
}
if(root.right!=null){
dfs(root.right,false);
}
} }
