二叉树的遍历（递归与非递归）
非递归遍历
- 前序遍历
对于非递归的树遍历，通过一个stack进行原来递归的处理；前序遍历是左子树遍历的时候，进行入栈的操作进行val的res的入栈操作。当stack栈空的时候结束；
前序遍历非递归(Leetcode 144)
vector<int> preorderTraversal(TreeNode* root)
{
stack<TreeNode*> stack;
vector<int> res;
TreeNode* p = root;
while(p != nullptr || !stack.empty()){
while(p != nullptr){
res.push_back(p->val); // 入栈时，将val加入res中
stack.push(p);
p = p->left;
}
if(!stack.empty()){
p = stack.top();
stack.pop();
p = p->right;
}
}
return res;
}
- 非递归中序遍历(Leetcode 94)
vector<int> inorderTraversal(TreeNode* root)
{
stack<TreeNode*> stack;
vector<int> res;
TreeNode* p = root;
while(p || !stack.empty()){
while(p){
stack.push(p);
p = p->left;
}
if(!stack.empty()){
p = stack.top();
stack.pop();
res.push_back(p->val);
p = p->right;
}
}
return res;
}
-
后序遍历的方法较多(Leetcode 145)
（1）使用reverse方法
前序遍历的顺序：根节点–>左节点–>右节点
后序遍历的顺序：左节点–>右节点–>根节点
因此如果遍历的顺序是：根节点–>右节点–>左节点；那么再进行reverse的一个翻转操作就可以了；
vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> stack; vector<int> res; TreeNode* p = root; while(p || !stack.empty()){ while(p){ stack.push(p); res.push_back(p->val); p = p->right; } if(!stack.empty()){ p = stack.top(); stack.pop(); p = p->left; } } reverse(res.begin(),res.end()); return res; }
（2）使用pre的nullptr的空指针操作
利用空指针的核心：当访问一个节点的右子节点之后，来进行父结点已经访问过的确认；
利用pre的空指针操作，来进行记录上一个访问的结点。如果该节点已经访问过，那么直接进行出栈操作就好；
另外注意一个问题，网上出现pre空指针操作的一个先出栈，再入栈的版本，还说是好的代码版本实在是有点扯淡。虽然总的来看思路一致，但是对于初学者而言无疑增加了的理解负担，所以先上自己的空指针版本；
vector<int> postorderTraversal(TreeNode* root)
{
stack<TreeNode*> stack;
vector<int> res;
TreeNode* cur = root;
TreeNode* pre = nullptr;
while(cur || !stack.empty()){
while(cur){
stack.push(cur);
cur = cur->left;
}
cur = stack.top();
if(cur->right == pre || cur->right == nullptr){
res.push_back(cur->val);
stack.pop();
pre = cur;
cur = nullptr;
}
else{
cur = cur->right;
}
}
return res;
}
下面是两次入栈的代码，基本逻辑一致，但是不推荐：
image.png
