1.三种非递归遍历（栈）
先序 + 中序
思路：就拿先序遍历为例来说吧。
1.访问根节点，根节点入栈，进入左子树。
2.访问左子树的根节点，根节点入栈，进入下一层左子树。
3.重复直到当前节点为空。即到达了最左下方的节点
4.如果栈不为空，就从栈顶取出节点，进入其右子树
5.直到当前节点和栈都为空时，结束。（栈为空就是所有的入栈的节点的右子树都访问过了。当前节点为空就代表所有的节点都访问过了）
先序遍历实现代码：
class Solution
{
public:
vector<int> preorderTraversal(TreeNode *root)
{
vector<int> ans;
if (!root)
return ans;
auto cur = root;
std::stack<TreeNode *> st;
while (cur || !st.empty())
{
while (cur)
{
ans.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
if (!st.empty())
{
cur = st.top();
st.pop();
cur = cur->right;
}
}
return ans;
}
};
中序遍历实现代码：
class Solution
{
public:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> ans;
if (!root)
return ans;
auto cur = root;
std::stack<TreeNode *> st;
while (cur || !st.empty())//注意是一定要有cur这个条件的！！！
{
while (cur)
{
st.push(cur);
cur = cur->left;
}
if (!st.empty())
{
cur = st.top();
ans.push_back(cur->val);
st.pop();
cur = cur->right;
}
}
return ans;
}
};
后序
思路：后序的遍历要比前面的两种复杂一些。因为在前面我们的思路就是**进左子树，然后从左子树返回，退栈，进右子树。**而在后序中，我们是必须先访问完左右子树才能退栈，访问根节点。那么我们如何知道是从哪个子树返回的呐？其实也很简单的啦。就设置一个标记（tag），左为0，右为1。如果tag1就退栈返回，如果不为1，就修改它的tag1，往右子树走就行了
后序遍历实现代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
struct Node
{
TreeNode *tree_node;
bool tag = false; //作为标志哦 ?
Node(TreeNode *node, bool flag = false) : tree_node(node), tag(flag)
{
}
};
class Solution
{
public:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> ans;
if (!root)
return ans;
auto cur = root;
std::stack<Node *> st;
while (cur || !st.empty())
{
while (cur)
{
st.push(new Node(cur, false));
cur = cur->left;
}
if (!st.empty())
{
cur = st.top()->tree_node;
if (false == st.top()->tag)
{
st.top()->tag = true;
cur = cur->right;
}
else
{
ans.push_back(cur->val);
st.pop();
cur = nullptr; //这里一定要置空！！！
}
}
}
return ans;
}
};
总结：三种不同的遍历过程的搜索路径是相同的，不同的仅是三次经过节点时哪一次访问节点。但无论那次经过节点访问时，在第一次经过节点时，都需要保留其节点信息。以便返回时，找到其右子树或者该节点。
tips：有没有发现在保存结果的时候，我们
保存或者打印的那一步就是对应于根节点的操作。与先序，中序等遍历的顺序 是一样的！！！
2.层次遍历（队列+BFS）
思路：先访问的节点的其孩子也将先访问，后访问的节点的其孩子也将后访问，先进先出与队列的形式相同哦
1.队头节点出队，并访问出队节点
2.出队节点的左右孩子依次入队
层次遍历实现代码：
class Solution
{
public:
vector<vector<int>> levelOrder(TreeNode *root)
{
vector<vector<int>> res;
if (!root)
return res;
std::queue<TreeNode *> QQ;
QQ.push(root);
while (!QQ.empty())
{
int count = QQ.size();
vector<int> vv;
for (int i = 0; i < count; i++)
{
auto tmp = QQ.front();
vv.push_back(tmp->val);
QQ.pop();
if (tmp->left)
QQ.push(tmp->left);
if (tmp->right)
QQ.push(tmp->right);
}
res.push_back(vv);
vv.clear();
}
return res;
}
};