前言
在前一篇文章中我分享了关于多叉树遍历的相关知识与C++代码，这一篇文章将主要介绍二叉树的遍历。二叉树是一种特殊的多叉树，它的每个节点的子节点至多为两个，接下来我们将学习如何进行二叉树的深度优先遍历和广度优先遍历。
为了让大家更容易理解，我们以下图中的树为例进行详解：
其中若我们以A为根结点，则{B,C,D}为左子树，{C,D,F}为右子树。
深度优先遍历
深度优先遍历根据父节点和子节点的访问顺序不同，将其分为了三类：
- 前序遍历：首先访问根节点，其次访问其左子树，最后访问右子树；
- 中序遍历：首先访问左子树，其次访问根节点，最后访问右子树；
- 后序遍历：首先访问左子树，其次访问右子树，最后访问根节点；
先序遍历
遍历结果为A → B → D → E → C → F → G
C++递归实现
具体实现代码如下：
void preorder(TreeNode* root, vector<int>& res){
if(nullptr == root) return;
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
C++非递归实现
具体代码如下：
void preorder_stack(TreeNode* root, vector<int>& res){
if(nullptr == root) return;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* node = s.top();
res.push_back(node->val);
s.pop();
if(nullptr != node->right) s.push(node->right);
if(nullptr != node->left) s.push(node->left);
}
}
除此以外，还有一种更容易理解的方式，可以使用标记的方式来进行访问，将栈中的元素设置为<node, visitable>，其中的visitable指的当前节点node是否是可访问的，如果该节点是可访问的，则输出访问。
在先序遍历中，令右节点先入栈，左节点后入栈，入栈之后更改根结点访问方式，将其visitable更改为可访问，将其输出，直至栈空。具体代码如下：
void preorder_flag(TreeNode* root, vector<int>& res){
if(nullptr == root) return;
stack<pair<TreeNode*, bool>> s;
s.push({root, false});
while(!s.empty()){
auto [node, visitalbe] = s.top();
s.pop();
if(visitalbe == true){
res.push_back(node->val);
}else{
if(nullptr != node->right) s.push({node->right, false});
if(nullptr != node->left) s.push({node->left, false});
s.push({node,true});
}
}
}
中序遍历
遍历结果为D → B → E → A → F → C → G
C++递归实现
void inorder(TreeNode* root, vector<int>& res){
if(nullptr == root) return;
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
C++非递归实现
同样的，我们使用标记的方式来进行实现，具体代码如下：
void inorder_flag(TreeNode* root, vector<int>& res){
if(nullptr == root) return;
stack<pair<TreeNode*, bool>> s;
s.push({root, false});
while(!s.empty()){
auto [node, visitalbe] = s.top();
s.pop();
if(visitalbe == true){
res.push_back(node->val);
}else{
if(nullptr != node->right) s.push({node->right, false});
s.push({node,true});
if(nullptr != node->left) s.push({node->left, false});
}
}
}
后序遍历
遍历结果为D → E → B → F → G → C → A
C++递归实现
void postorder(TreeNode* root, vector<int>& res){
if(nullptr == root) return;
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);
}
C++非递归实现
二叉树的后续遍历与二叉树的前序遍历有着特殊的关系，如下：
前序遍历：（根左右） ----逆向---- （右左根）
若我们采用前序遍历的方式，但遍历顺序为根右左，此时将这种顺序所得的结果进行逆向则得到的顺序则为左右根，恰好为后序遍历的顺序。而想要利用前序遍历的方式将遍历顺序转为根右左并不难，只需要将前序遍历中的左节点和右节点入栈的顺序进行颠倒即可。
代码如下：
void postorder_stack(TreeNode* root, vector<int>& res){
if(nullptr == root) return;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* node = s.top();
s.pop();
res.push_back(node->val);
if(nullptr != node->left) s.push(node->left);
if(nullptr != node->right) s.push(node->right);
}
reverse(res.begin(), res.end());
}
除此以外，我们还可以使用标记的方式，具体代码如下：
void postorder_flag(TreeNode* root, vector<int>& res){
if(nullptr == root) return;
stack<pair<TreeNode*, bool>> s;
s.push({root, false});
while(!s.empty()){
auto [node, visitable] = s.top();
s.pop();
if(visitable == true){
res.push_back(node->val);
}else{
s.push({node, true});
if(nullptr != node->right) s.push({node->right, false});
if(nullptr != node->left) s.push({node->left, false});
}
}
}
广度优先遍历
二叉树的广度优先遍历和多叉树的广度优先遍历实现是一致的，分为两种。递归实现的方式主要是先求得树的深度，然后使用递归的方式进行访问；非递归的方式主要是使用队列来进行实现。
C++递归实现
我们首先需要求得该多叉树的深度，在进行遍历的时候利用traverLayer找到对应的那一行输出遍历，直至到最后一行节点结束。具体代码如下：
void levelorder(TreeNode* root, int level, vector<vector<int>>& res){
if(nullptr == root) return;
if(res.size()<=level) res.resize(level+1);
res[level].push_back(root->val);
if(nullptr != root->left) levelorder(root->left, level+1, res);
if(nullptr != root->right) levelorder(root->right, level+1, res);
}
C++非递归实现
基本思路是从根结点开始，将其压入队列中，每从队列中弹出一个节点，就将该节点的孩子节点压入队列中，直至队列中的元素为空则访问结束。
具体实现代码如下：
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == nullptr) return res;
queue<pair<TreeNode*, int>> q;
q.push({root, 0});
while(!q.empty()){
auto [node, level] = q.front();
q.pop();
if(res.size()<=level) res.resize(level+1);
res[level].push_back(node->val);
if(nullptr != node->left) q.push({node->left, level+1});
if(nullptr != node->right) q.push({node->right, level+1});
}
return res;
}
