二叉树的前序遍历、中序遍历、后续遍历的非递归实现
前序遍历：先访问该节点，然后访问该节点的左子树和右子树；
中序遍历：先访问该节点的左子树，然后访问该节点，再访问该节点的右子树；
后序遍历：想访问该节点的左子树和右子树，然后访问该节点。
递归遍历
对于递归遍历比较简单：
void preorder(treenode* root) {
if (root == null)
return;
visit(root);
preorder(root->left);
preorder(root->right);
}
void inorder(treenode* root) {
if (root == null)
return;
inorder(root->left);
visit(root);
inorder(root-left);
postorder(root->right);
visit(root);
}
非递归（迭代）遍历
非递归实现在遍历根节点后还要回来，因此要基于栈（先进后出）来保存节点。
注：二叉树遍历的非递归实现文章里有不同的实现方式，更易于理解记忆。
前序遍历
压入顺序：右子树->左子树->根节点
使得访问的时候的顺序成为：根->左子树->右子树
vector preordertraversal(treenode* root) {
vector result;
stack s;
if (root == null)
return result;
s.push(root);
while(!s.empty()) {
treenode* p = s.top();
s.pop();
result.push_back(p->val);
if (p->right)
s.push(p->right);
if (p->left)
s.push(p->left);
}
return result;
}
中序遍历
压入顺序：右子树->根->左子树
只有当左子树已经访问完后，才能访问根节点
对于任一结点p，
1)若其左孩子不为空，则将p入栈并将p的左孩子置为当前的p，然后对当前结点p再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的p置为栈顶结点的右孩子；
3)直到p为null并且栈为空则遍历结束
vector inordertraversal(treenode* root) {
vector result;
stack s;
if (root == null)
return result;
treenode* p = root;
while (!s.empty() || p != null) {
if (p != null) {
// push 左子树入栈
s.push(p);
p = p->left;
} else {
// 左子树为空时，访问该节点，然后访问右子树
p = s.top();
result.push_back(p->val);
s.pop();
p = p->right;
}
}
return result;
}
后序遍历
先压入根，然后是右子树，最后左子树
要求最后访问根节点，即访问该根节点时必须访问完左子树和右子树，我们只需要保证访问某一节点时，该节点的右子树已经被访问，否则需要将该节点重新压入栈。
对于任一结点p，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。
vector postordertraversal(treenode* root) {
vector result;
if (root == null)
return result;
stack s;
treenode* p = root; //当前正访问的节点
treenode* q; //记录刚刚访问过的节点
do{
while (p != null) {
s.push(p);
p = p->left;
}
q = null;
while (!s.empty()) {
p = s.top();
s.pop();
if (p->right == q) { //当右子树已经访问过了，才可以访问根
result.push_back(p->val);
q = p; //记录刚刚访问过的节点
} else {
s.push(p); //第一次访问到该节点，需要将它重新入栈
p = p->right;
break;
}
}
} while (!s.empty());
return result;
}
微流控芯片检测技术_微流控芯片是否有前景
Moku 云编译介绍
吉利商用车湖州基地项目落户南太湖新区
谷歌持续精简，但核心业务持续增长
中国电信基于天翼医疗云专区的整体信息化解决方案
二叉树的前序遍历、中序遍历、后续遍历的非递归实现
数字化的深耕与构建：华为数字能源的立体版图
魅族MX首张官方图曝光 M9降价为其开道
强油循环风冷变压器发生“备用冷却器投入”信号时，怎么办？
多方面因素扰乱供需平衡 2023年内存市场依旧不平稳
什么是5G核心网的微服务
FPC的结构层次的不同性质介绍
10.5英寸iPad Pro怎么样？新iPad Pro评测：未来长时间内的主力生产工具
电子工程师结合创造性与习惯
简单的mems陀螺仪姿态算法介绍
软通动力天枢元宇宙研究院在南京江宁高新区揭牌成立
用于智能电网的基于红外的无线电力技术
智能家居的新入口，将全方位管理你和你的家
电动车电池的保养方法_电动车电池的容量怎么看
提高电脑开机速度的技巧方法
中序遍历：先访问该节点的左子树，然后访问该节点，再访问该节点的右子树；
后序遍历：想访问该节点的左子树和右子树，然后访问该节点。
递归遍历
对于递归遍历比较简单：
void preorder(treenode* root) {
if (root == null)
return;
visit(root);
preorder(root->left);
preorder(root->right);
}
void inorder(treenode* root) {
if (root == null)
return;
inorder(root->left);
visit(root);
inorder(root-left);
postorder(root->right);
visit(root);
}
非递归（迭代）遍历
非递归实现在遍历根节点后还要回来，因此要基于栈（先进后出）来保存节点。
注：二叉树遍历的非递归实现文章里有不同的实现方式，更易于理解记忆。
前序遍历
压入顺序：右子树->左子树->根节点
使得访问的时候的顺序成为：根->左子树->右子树
vector preordertraversal(treenode* root) {
vector result;
stack s;
if (root == null)
return result;
s.push(root);
while(!s.empty()) {
treenode* p = s.top();
s.pop();
result.push_back(p->val);
if (p->right)
s.push(p->right);
if (p->left)
s.push(p->left);
}
return result;
}
中序遍历
压入顺序：右子树->根->左子树
只有当左子树已经访问完后，才能访问根节点
对于任一结点p，
1)若其左孩子不为空，则将p入栈并将p的左孩子置为当前的p，然后对当前结点p再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的p置为栈顶结点的右孩子；
3)直到p为null并且栈为空则遍历结束
vector inordertraversal(treenode* root) {
vector result;
stack s;
if (root == null)
return result;
treenode* p = root;
while (!s.empty() || p != null) {
if (p != null) {
// push 左子树入栈
s.push(p);
p = p->left;
} else {
// 左子树为空时，访问该节点，然后访问右子树
p = s.top();
result.push_back(p->val);
s.pop();
p = p->right;
}
}
return result;
}
后序遍历
先压入根，然后是右子树，最后左子树
要求最后访问根节点，即访问该根节点时必须访问完左子树和右子树，我们只需要保证访问某一节点时，该节点的右子树已经被访问，否则需要将该节点重新压入栈。
对于任一结点p，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。
vector postordertraversal(treenode* root) {
vector result;
if (root == null)
return result;
stack s;
treenode* p = root; //当前正访问的节点
treenode* q; //记录刚刚访问过的节点
do{
while (p != null) {
s.push(p);
p = p->left;
}
q = null;
while (!s.empty()) {
p = s.top();
s.pop();
if (p->right == q) { //当右子树已经访问过了，才可以访问根
result.push_back(p->val);
q = p; //记录刚刚访问过的节点
} else {
s.push(p); //第一次访问到该节点，需要将它重新入栈
p = p->right;
break;
}
}
} while (!s.empty());
return result;
}
微流控芯片检测技术_微流控芯片是否有前景
Moku 云编译介绍
吉利商用车湖州基地项目落户南太湖新区
谷歌持续精简，但核心业务持续增长
中国电信基于天翼医疗云专区的整体信息化解决方案
二叉树的前序遍历、中序遍历、后续遍历的非递归实现
数字化的深耕与构建：华为数字能源的立体版图
魅族MX首张官方图曝光 M9降价为其开道
强油循环风冷变压器发生“备用冷却器投入”信号时，怎么办？
多方面因素扰乱供需平衡 2023年内存市场依旧不平稳
什么是5G核心网的微服务
FPC的结构层次的不同性质介绍
10.5英寸iPad Pro怎么样？新iPad Pro评测：未来长时间内的主力生产工具
电子工程师结合创造性与习惯
简单的mems陀螺仪姿态算法介绍
软通动力天枢元宇宙研究院在南京江宁高新区揭牌成立
用于智能电网的基于红外的无线电力技术
智能家居的新入口，将全方位管理你和你的家
电动车电池的保养方法_电动车电池的容量怎么看
提高电脑开机速度的技巧方法