LeetCode题目链接
二叉树的前序遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/ 二叉树的中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/ 二叉树的后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/
二叉树的遍历方法有两种，分别是递归法和迭代法；实际使用中由于系统调用栈有限制，使用递归法可能会导致栈溢出，这里记录三种遍历的迭代做法。最后，介绍二叉树层序遍历的两种方法。
迭代遍历法借助辅助栈实现，下面是二叉树节点的定义，使用链表实现。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
前序遍历
前序遍历的顺序是中左右，每次先处理中间节点，那么先将根节点入栈，然后将右孩子入栈，再将左孩子入栈。先右后左的原因是因为入栈顺序和处理顺序是相反的。前序遍历的处理代码如下：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
if (root == NULL) {
return res;
}
st.push(root);
while (!st.empty()) {
TreeNode *cur = st.top();
st.pop();
res.push_back(cur->val);
if (cur->right) st.push(cur->right);
if (cur->left) st.push(cur->left);
}
return res;
}
};
中序遍历
中序遍历处理顺序为左中右，先访问二叉树顶部的节点，随后逐层向下访问直到树最左侧的节点，再开始处理节点，这导致处理节点的顺序和访问节点的顺序不一致。中序遍历的迭代法如下所示：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
if (root == NULL) {
return res;
}
TreeNode *cur = root;
while (cur!=NULL || !st.empty()) {
if (cur != NULL) {
if (cur) st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
};
后序遍历
先序遍历是中左右，后续遍历是左右中，那么只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了。后序遍历的代码如下所示：
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
if (root == NULL) {
return res;
}
st.push(root);
while (!st.empty()) {
TreeNode *cur = st.top();
st.pop();
if (cur->left) st.push(cur->left);
if (cur->right) st.push(cur->right);
res.push_back(cur->val);
}
reverse(res.begin(), res.end());
return res;
}
};
统一的迭代遍历法
参考https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html 每次在待处理节点入栈后，加入一个NULL节点作为标记，之后在遇到NULL节点时处理栈中的下一个节点。需要注意的是，这种方法效率不高，节点可能会多次入栈。
层序遍历
// 迭代遍历，BFS基于队列
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> q;
if (root == NULL) {
return res;
}
q.push(root);
while (!q.empty()) {
int size =q.size();
vector<int> layer;
for (int i = 0; i < size; ++i) {
TreeNode *cur = q.front();
q.pop();
layer.push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
res.push_back(layer);
}
return res;
}
};
// 递归，DFS
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> q;
if (root == NULL) {
return res;
}
order(0, root, res);
return res;
}
// DFS, 递归
void order(int depth, TreeNode *cur, vector<vector<int>> &res) {
if (cur == NULL) return;
if (res.size() == depth) res.push_back(vector<int>());
res[depth].push_back(cur->val);
order(depth + 1, cur->left, res);
order(depth + 1, cur->right, res);
}
};