二叉树的遍历【C++】
对于二叉树系列的题，必须要会遍历二叉树。
遍历的有：深度优先：前序、中序、后序，广度优先：层序遍历
什么序是指处理根节点在哪个位置，比如前序是指处理节点顺序：根左右。
接下来要说明的是：选用递归实现还是迭代实现，一般来说递归法和迭代法可以相互转化。
递归有固定的流程：
- 递归函数的参数和返回值
- 终止条件
- 单层递归的逻辑
递归顺序分为：
- 访问顺序：都是根左右
- 处理顺序：和什么序一致，和题目描述有关，这是二叉树题目的关键
迭代常常使用栈或者队列来实现
题目链接：
二叉树的前序遍历
二叉树的中序遍历
二叉树的后序遍历
二叉树的层序遍历
那么这4种遍历顺序和2种实现方式就有4 * 2 == 8种代码实现：
递归前序
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res; //存放结果
preorder(root, res); //递归调用
return res;
}
void preorder(TreeNode* root, vector<int>& res) { //1.递归函数的参数和返回值
if (root == nullptr) { //2.终止条件
return;
}
res.push_back(root -> val); //3.单层递归的逻辑
preorder(root -> left, res); //根左右
preorder(root -> right, res);
}
};
递归中序
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
Traversal(root, res);
return res;
}
void Traversal(TreeNode* root, vector<int>& res) {
if (root == nullptr) {
return;
}
Traversal(root -> left, res);
res.push_back(root -> val);
Traversal(root -> right, res);
}
};
递归后序
class Solution {
public:
void dfs(TreeNode* head, vector<int>& res){
if (head == nullptr){
return;
}
dfs(head -> left, res);
dfs(head -> right, res);
res.push_back(head -> val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
dfs (root, res);
return res;
}
};
可以看出：递归法的前中后序的区别在于处理根节点的顺序不同。
迭代前序
使用代码随想录的图片：
注意：栈是先入后出，所以要先放入右节点。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) { //边界判断
return res;
}
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* cur = stk.top();
stk.pop();
res.push_back(cur -> val);
if (cur -> right) { //关键
stk.push(cur -> right);
}
if (cur -> left) {
stk.push(cur -> left);
}
}
return res;
}
};
迭代中序
代码随想录的图片：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> 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;
}
};
迭代后序：
由上图可知：只需要将先序遍历调整左右顺序，并反转结果数组，就能得到后序遍历。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
if (root == nullptr) {
return res;
}
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
res.push_back(node -> val);
if (node -> left) stk.push(node -> left); //和先序区别
if (node -> right) stk.push(node -> right);
}
reverse(res.begin(), res.end()); //反转结果
return res;
}
};
递归层序
访问顺序：根左右
处理顺序：使用一个depth变量，记录当前在哪一层
class Solution {
public:
void order(TreeNode* cur, vector<vector<int>>& result, int depth)
{
if (cur == nullptr) return;
if (result.size() == depth) result.push_back(vector<int>());
result[depth].push_back(cur->val); //放入对应层
order(cur->left, result, depth + 1);
order(cur->right, result, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
int depth = 0;
order(root, result, depth);
return result;
}
};
迭代层序
代码随想录的动态图如下：
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que; //队列实现
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
总结：本文介绍了二叉树的8种实现方法，4种遍历方式必须会一种。