二叉树遍历--(前 中 后 层序)

1.前序遍历

前序遍历顺序 先访问根节点再左子树 最后右子树  

根->左->右

#include <iostream>
#include <stack>struct TreeNode
{int val;TreeNode* left;TreeNode* right;TreeNode(int v):val(v),left(nullptr),right(nullptr){}
};//后序 左->右->根 先访问左子树 再访问右子树 最后访问根
//双栈法
//1.先实现 根->右->左 (先入左孩子)
//2.将该顺序入栈 再出栈变为 左->右->根
void PostT(TreeNode*root)
{if(root==nullptr)return;std::stack<TreeNode*> s1,s2;s1.push(root);while (!s1.empty()){auto top=s1.top();s1.pop();s2.push(top);if(top->left) s1.push(top->left);//先push左孩子if(top->right) s1.push(top->right);}while (!s2.empty()){auto top=s2.top();std::cout<<top->val<<" ";s2.pop();}std::cout<<std::endl;
}int main() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);PostT(root);return 0;
}

1.先定义一个栈，栈是先进后出。每新进一个节点，先输出值 再把它的左右孩子压入到栈中。先压入哪个孩子？先压右孩子 再压左孩子。这样出栈时先出左孩子 符合根->左->右顺序

2.后序遍历

后序遍历顺序 左->右->根 左右子树访问完 最后访问根节点

#include <iostream>
#include <stack>struct TreeNode
{int val;TreeNode* left;TreeNode* right;TreeNode(int v):val(v),left(nullptr),right(nullptr){}
};//后序 左->右->根 先访问左子树 再访问右子树 最后访问根
//双栈法
//1.先实现 根->右->左 (先入左孩子)
//2.将该顺序入栈 再出栈变为 左->右->根
void PostT(TreeNode*root)
{if(root==nullptr)return;std::stack<TreeNode*> s1,s2;s1.push(root);while (!s1.empty()){auto top=s1.top();s1.pop();s2.push(top);if(top->left) s1.push(top->left);//先push左孩子if(top->right) s1.push(top->right);}while (!s2.empty()){auto top=s2.top();std::cout<<top->val<<" ";s2.pop();}std::cout<<std::endl;
}int main() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);PostT(root);return 0;
}

前序 根->左->右    后序 左->右->根

我们可以用双栈法来解决，用一个栈来完成前序遍历 并把遍历的值存入另一个栈了

这样 前序 根左右 出栈-> 右左根 但和后序不一样怎么办？

把前序压入左右子树的顺序该一下变为 先压左 再压右  =>  根->右->左

这样出栈就可以变为 后序 左->右->根

3.中序遍历

先访问完左子树 再根 最后右子树 

左->根->右

我们先循环把左孩子压入栈 直到没有左孩子，左孩子为空相当于左子树遍历完了，按照顺序我们就可以输出根节点值(此时栈顶就是要输出的节点)，最后访问右子树。再以右孩子为根节点 继续循环压入左孩子... 

#include <iostream>
#include <stack>struct TreeNode
{int val;TreeNode* left;TreeNode* right;TreeNode(int v):val(v),left(nullptr),right(nullptr){}
};
//中序 左->根->右
void InT(TreeNode* root) 
{if(root==nullptr)return;std::stack<TreeNode*> s;TreeNode* cur=root;while(cur||!s.empty()){//把根/左孩子全入栈while(cur){s.push(cur);cur=cur->left;}//此时栈顶元素 为树的最左节点 它没有左孩子 //中序左 根 右  左为空 直接输出根auto top=s.top();std::cout<<top->val<<" ";s.pop();//再继续找右孩子的最左节点cur=top->right;}std::cout<<std::endl;
}
int main() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);InT(root);return 0;
}

4.层序遍历

自顶向下 从左到右，进行输出。

#include <iostream>
#include <queue>
struct TreeNode
{int val;TreeNode* left;TreeNode* right;TreeNode(int v):val(v),left(nullptr),right(nullptr){}
};
void LevelT(TreeNode*root)
{if(root==nullptr)return;std::queue<TreeNode*> q;q.push(root);while(!q.empty()){int tmp=q.size();while(tmp){auto cur=q.front();std::cout<<cur->val<<" ";q.pop();tmp--;if(cur->left)q.push(cur->left);if(cur->right)q.push(cur->right);}std::cout<<std::endl;}
}

用一个队列存下一层需要输出的节点，每pop一个节点 就把它的左右孩子push入队，直到栈为空。可以向上面用一个tmp记录当前层需要pop的节点，每一行打印一层。

遍历方式	顺序定义	实现思路	关键点/数据结构
前序遍历	根 → 左 → 右	栈：根入栈 → 先右后左入栈	stack<TreeNode*>
中序遍历	左 → 根 → 右	栈：一路左压栈 → 出栈访问 → 处理右	stack<TreeNode*>
后序遍历	左 → 右 → 根	双栈：根 → 左 → 右 入辅助栈，翻转为后序	stack<TreeNode*> s1, s2
层序遍历	一层一层 → 从左到右	队列：每层记录当前层节点个数 → 入队左右孩子	queue<TreeNode*>