DFS Summary - Leetcode

0.Basic Concepts

Depth First Search (DFS) is a method for traversing or searching tree or graph data structures.

1.When do we apply DFS?

It is frequently used to
  1) explore some features/characteristics in the tree/graph.
  2) search specific nodes/paths/connected components(int the graph)

2. Typical Examples

Some tips:
1. A leaf node can only be represented as "node.left==null && node.right==null".


explore tree features:
[100] Same Tree
[101] Symmetric Tree
[104] Maximum Depth of Binary Tree
[110] Balanced Binary Tree

Search for specific node/connected components
[200] Number of Islands
[323] Number of Connected Components in an Undirected Graph

Path-related
[112] Path Sum
[129] Sum Root to Leaf Numbers
[337] House Robber III
[366] Find Leaves of Binary Tree

Related recursive problems
[105] Construct Binary Tree from Preorder and Inorder Traversal
[108] Convert Sorted Array to Binary Search Tree