Depth-First Search (DFS)

Concept

In tree traversal, we can use DFS to do pre-order, in-order and post-order traversal.

Implementation

1.Recursion + set. (using implicit STACK in recursion, which is known as "Call Stack")

2.Stack + set. (without recursion, using explicit STACK)

Template - recursion

We stop when we find the first answer, but maybe this answer is not what we want. Maybe it's not the shortest path, or we want to find all possible pathes we have.

Hint: Add one more parameter to indicate the shortest path you have already found.

bool DFS(int cur, int target, set<int> visited) { if(cur == target) return true; for(next : each neighbor of cur) { if(next is not in visited) { add next into visited; if(DFS(next, target, visited) == true) return true; } } return false; }

[Medium] No.200 Number of Islands

Approach: DFS

Time Complexity: O(M*N), where M is the number of row in the grid, N is the number of col in the grid.

Space Complexity: O(M*N), dfs using recusion and call stack. In the worst case, all the grids are lands and all put into the stack. Thus, the total space used is M*N.

using visited class Solution { public: vector<pair<int,int>> dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}}; void dfs(vector<vector<char>>& grid, int x, int y, vector<vector<bool>>& visited) { //base case if(visited[x][y] == true || grid[x][y] == '0') return; //find neighbor for(auto dir : dirs) { if(dir.first + x >= grid.size() || dir.second + y >= grid[0].size() || dir.first + x < 0 || dir.second + y < 0) { continue; } visited[x][y] = true; dfs(grid, dir.first + x, dir.second + y, visited); } } int numIslands(vector<vector<char>>& grid) { int ans = 0; if(grid.size() == 0) return 0; int row = grid.size(); int col = grid[0].size(); vector<vector<bool>> visited(row, vector<bool> (col, false)); for(int i = 0 ; i < grid.size() ; i++) { for(int j = 0 ; j < grid[0].size() ; j++) { if(grid[i][j] == '1' && visited[i][j] == false) { dfs(grid, i, j, visited); ans++; } } } return ans; } };

without visited class Solution { public: vector<pair<int,int>> dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}}; void dfs(vector<vector<char>>& grid, int x, int y) { //base case if(grid[x][y] == '0') return; //find neighbor for(auto dir : dirs) { if(dir.first + x >= grid.size() || dir.second + y >= grid[0].size() || dir.first + x < 0 || dir.second + y < 0) { continue; } grid[x][y] = '0'; dfs(grid, dir.first + x, dir.second + y); } } int numIslands(vector<vector<char>>& grid) { int ans = 0; if(grid.size() == 0) return 0; int row = grid.size(); int col = grid[0].size(); for(int i = 0 ; i < grid.size() ; i++) { for(int j = 0 ; j < grid[0].size() ; j++) { if(grid[i][j] == '1') { dfs(grid, i, j); ans++; } } } return ans; } };

Template II - without recursion

If the depth of recursion is too high, you will suffer from stack overflow. In that case, use BFS or implement DFS using an explicit stack.

The while loop and stack is to simulate the system call stack during recursion.

bool DFS(int root, int target) { set<int> visited; stack<int> stk; stk.push(root); visited.insert(root); while(!stk.empty()) { int cur = stk.top(); stk.pop(); if(cur == target) return true; for(next : each neighbor of cur) { if(next is not in visited) { visited.insert(next); stk.push(next); } } } return false; }

[Medium] No.1120 Maximum Average Subtree

Approach: DFS with pair

Time Complexity: O(N), where N is the number of nodes in the tree.

Space Complexity: O(N), where N is the number of nodes in the tree.

class Solution { public: double ans = -1; pair<int,int> dfs(TreeNode* node) { double left = 0, right = 0; pair<int,int> pl, pr; int num = 1; //leaf node if(node->left == NULL && node->right == NULL) { if(node->val > ans) ans = node->val; return {node->val,1}; } //not leaf node if(node->left != NULL) { pl = dfs(node->left); left = pl.first; num += pl.second; } if(node->right != NULL) { pr = dfs(node->right); right = pr.first; num += pr.second; } ans = max(ans, (left + right + node->val) / num); return {left+right+node->val, num}; } double maximumAverageSubtree(TreeNode* root) { if(root == NULL) return 0; dfs(root); return ans; } };