二叉树的遍历，前序，中序，后序三种，三种遍历方式，分别用BFS(Breadth First Search)和DFS(Depth First Search)来实现下。
DFS算法比较好实现，这里记录下BFS的实现
遍历的基本结构：
while(root || !stk.empty()){
while(root){
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
}前序：
/**
* Definition for a binary tree node.
* 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 {
private:
vector<int> result;
public:
void bfs(TreeNode* root){
if(!root) return;
stack<TreeNode*> stk;
while(root || !stk.empty()){
while(root){
stk.push(root);
result.emplace_back(root->val);
root = root->left;
}
root = stk.top();
stk.pop();
root = root->right;
}
}
vector<int> preorderTraversal(TreeNode* root) {
bfs(root);
return result;
}
};我们拿到一个节点后就往这个节点的左边开始访问，直到这个节点没有左节点为止，从二叉树的构造看，首次访问到某个节点该节点就是子树的根节点，前序便利根节点就在前面，所以只要访问到了节点就给他放进结果里就可以了。
while(root){
stk.push(root);
result.emplace_back(root->val);
root = root->left;
}左边路访问完成后，栈里面装的都是左边路的根节点，拿到左边路的最后一个节点，它没有左节点，获取右节点。如果右节点空的，但是栈里面还有其他的左边路的节点，所以循环得继续，访问刚才那个左边路最后节点的父节点，所以看大循环的判定条件是：
while(root || !stk.empty()){
...
...
...
}中序
这里有个疑问为什么前序和中序只是挪动一下输出节点的位置就可以实现，主要是因为，不管前序还是中序，都是先把左边路先入栈，在一条左边路访问结束后，判定栈顶元素是不是有右节点，如果有右节点，进入另一个循环，开始循环右节点的左边路，如果在访问右节点前把该节点输出，那么就是前序和中序了，访问之后就是后续。怎么区分前序和中序？不知道～背过的～～遗憾
/**
* Definition for a binary tree node.
* 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:
void bfs(TreeNode* root){
if(!root) return;
stack<TreeNode*> stk;
while(root || !stk.empty()){
while(root){
stk.push(root);
root = root->left;
}
root = stk.top();
result.emplace_back(root->val);
stk.pop();
root = root->right;
}
}
vector<int> inorderTraversal(TreeNode* root) {
bfs(root);
return result;
}
private:
vector<int> result;
};跟前序的不同点就是在什么时候输出节点，前序是在入栈某个节点的时候直接输出了，中序是在出栈的时候输出。
后序
这个后序比较麻烦，反正我是背过了，基于上面的分析，必然是在访问该节点的右节点之后输出该节点的，如果该节点本身就是叶子节点，右节点肯定是空，这个时候可以输出该节点，问题是怎么判定该节点的右子树已经访问完了，从背的答案里知道，如果这个节点有右节点，得把该节点保存一下，等把他右边的节点都输出完了再把存储的这个该节点输出。问题就是怎么知道访问完了，这么说不大明确，应该是说访问完了之后，怎么回到这个该节点，应为变量root空了以后会直接从stk出栈，因为左边路的节点都在栈里面，该节点的父节点其实就是stk中top的节点，所以top节点的右节点如果等于我们存储的该节点，就说明回来了，回来了就可以访问该存储的节点了。所以判定是否输出，就是当该节点没有右节点，或者存储的节点等于栈顶节点的右节点，可以输出。如果不是呢？当前节点有右节点，得去访问右节点，该节点得入栈；第二种可能不知道～背过
/**
* Definition for a binary tree node.
* 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:
void bfs(TreeNode* root){
if(!root) return;
TreeNode* prev;
stack<TreeNode*> stk;
while(root || !stk.empty()){
while(root){
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
if(!root->right || prev == root->right){
result.emplace_back(root->val);
prev = root;
root = nullptr;
}else{
stk.push(root);
root = root->right;
}
}
}
vector<int> postorderTraversal(TreeNode* root) {
bfs(root);
return result;
}
private:
vector<int> result;
};反正就这么写，就可以了～不要试图理解它，感受它，背过它～～～