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.
[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
without visited
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.
[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.