经典算法遍历分为两部分：
- 树的遍历
- 深度优先遍历
- 前序：迭代法（栈），递归法
- 中序：迭代法（栈），递归法
- 后序：迭代法（栈），递归法
- 广度优先
- 层次遍历：迭代法（队列），递归法
- 深度优先遍历
- 图的遍历
- 深度优先遍历 DFS
- 广度优先遍历 BFS
1 树的遍历
1.1 深度优先遍历
1.1.1 前序
迭代法：
迭代法的经典步骤：
- 1 根节点进栈
- 2 while(栈不为空)
- 3 取栈顶元素，弹出栈顶元素
- 4 存取栈顶元素
- 5 将栈顶元素的右左孩子进栈（由于栈是先进后出，所以需要先进栈右孩子，再进栈左孩子）
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
result.push_back(node->val);
if (node->right) st.push(node->right); // 右（空节点不入栈）
if (node->left) st.push(node->left); // 左（空节点不入栈）
}
return result;
}
};
递归法：
经典步骤：
- 处理自身节点
- 递归处理左孩子节点
- 递归处理右孩子节点
class Solution {
public:
void traversal(TreeNode* cur, vector& vec) {
if (cur == NULL) return;
vec.push_back(cur->val); // 中
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
}
vector preorderTraversal(TreeNode* root) {
vector result;
traversal(root, result);
return result;
}
}; 1.1.2 中序
中序的递归法不用讲，重点介绍一下迭代法。 中序的遍历顺序为左中右，所以需要BFS进入最左下角的元素，再中间，再右边。 中序遍历的经典步骤：- 1 根节点进栈
- 2 while(栈不为空， cur存在)，之所以这里需要两个或的判断条件，因为会出现栈为空，但是右孩子还未遍历的情况。
- 3 如果cur不为空，则一直往左下角走
- 4 如果cur为空，则取出栈顶元素（回溯），存取栈顶元素，然后走向右边
class Solution {
public:
vector inorderTraversal(TreeNode* root) {
vector result;
stack st;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) { // 指针来访问节点，访问到最底层
st.push(cur); // 将访问的节点放进栈
cur = cur->left; // 左
} else {
cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
st.pop();
result.push_back(cur->val); // 中
cur = cur->right; // 右
}
}
return result;
}
};
1.1.3 后序
后序的递归法依然不需要讲，只需要关注迭代法。
后序的遍历顺序为左右中，如果我们将先序的右左孩子进栈变成左右孩子进栈，则遍历顺序变成中右左，最后将遍历顺序翻转，则变成了左右中。
1.2 广度优先遍历
1.2.1 层次遍历
迭代法：使用队列，需要注意的是，队列中每层元素需要做一波处理。vector> &result;
void BFS(ListNode *root) {
if (root == nullptr)
return ;
queue que;
que.push(root);
while (!que.empty()) {
vector path;
int size = que.size();
for (int i = 0; i < size; i++) {
int node = que.front();
que.pop();
path.push_back(node->val);
if (root->left)
que.push(root->left);
if (root->right)
que.push(root->right);
}
}
} vector<vector> &result;
void BFS(ListNode *root, int depth) {
if (root == nullptr)
return;
if (depth == result.size())
result.append(vector());
result[depth].append(root->val);
BFS(root->left, depth + 1);
BFS(root->right, dpeth + 1);
}2 图的遍历
2.1 深度优先遍历
深度优先遍历的经典步骤：- 1 判断是否访问过，访问过则退出，未访问则设置为访问状态。
- 2 上下左右四个方向（for循环），先判断是否越界，如果不越界则进入下一次递归。
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void DFS(vector<vector>& grid, vector<vector>& visited, int x, int y){
if (visited[x][y] || grid[x][y] == '0') return ;
visited[x][y] = true;
for(int i=0; i<4; i++){
int next_x = x + dir[i][0];
int next_y = y + dir[i][1];
if (next_x < 0 || next_x > grid.size()) || next_y < 0 || next_y > grid[0].size()) continue;
DFS(grid, visited, next_x, next_y);
}
}2.2 广度优先遍历
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void BFS(vector>& grid, vector>& visited, int x, int y){
queue> que;
que.push({x, y});
visited[x][y] = true;
while(!que.empty()){
for(int i=0; i<4; i++){
pair node = que.front(); que.pop();
int next_x = x + node.first;
int next_y = y + node.second;
if (next_x < 0 || next_x > grid.size() || next_y < 0 || next_y > grid[0].size()) continue;
if (grid[next_x][next_y] != '0' && !visited[next_x][next_y]){
que.push({next_x, next_y});
visited[next_x][next_y];
}
}
}
}