二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {
TreeNode* cur=root;
stack<TreeNode*> st;
vector<int> v;
while(cur||!st.empty())//如果cur为空，或者栈为空则结束
{
while(cur)
{v.push_back(cur->val);st.push(cur);cur=cur->left;
}
//左路节点全部被存入数组
TreeNode* top=st.top();//获取栈顶的节点，也就是最左边的节点
st.pop();//此时将该节点弹出，也就是左节点访问完，现在栈顶是根
cur=top->right;//子问题访问右子树}return v;}
};
思路：遍历内容存在数组中，用栈来进行辅助，先遍历左树，每遍历一个节点，就把该节点的地址放入栈中，把节点的值放入数组中（也就以为着根和左节点都放入里面了），之后左树为空，栈顶是最左边而且下面树的根，之后访问右节点，并把根弹出栈。

二叉树的中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> v;
TreeNode*cur=root;
while(cur||!st.empty())
{
while(cur)
{
st.push(cur);
cur=cur->left;
}
//走到最左边的节点,将这个最左边的节放入数组中
TreeNode* top=st.top();//栈顶此时是最左节点
v.push_back(top->val);//最左边的节点放入数组中
st.pop();//pop之后st.top是根节点
cur=top->right;//这个top是最左边的节点，最左边节点访问完，最左边节点已经放入数组，也就是根节点已经放入数组（它的左右节点为空），接下来访问左右节点}return v;}
};

二叉树的后续遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {TreeNode* cur=root;stack<TreeNode*> st;TreeNode* prev=nullptr;//用来记录上一个节点vector<int> v;while(cur||!st.empty()){while(cur){st.push(cur);cur=cur->left;}//先把左节点全部放入栈中TreeNode* top=st.top();//一个节点的右子树不为空：//1.右子树没有访问，访问右子树//2.右子树访问过了，访问根节点if(top->right==nullptr || top->right==prev)//如果右子树为空，或者访问过右子树了，直接把根放入数组{v.push_back(top->val);st.pop();prev=top;}else//没访问右子树或右子树不为空就去访问右子树{cur=top->right;}}return v;}
};