题目链接

二叉树的前序遍历

在这里插入图片描述

144. 二叉树的前序遍历

思路分析

既然要使用非递归的方式，那就必须要借助栈来进行处理，前序遍历的遍历顺序为中左右，因此我们从根节点开始遍历，将遇到的每一个节点入栈，并保存遇到的每一个节点，我们不断的去访问左子树，当访问到最后一个节点时，此时就该访问右子树，当栈不为空或当前节点不为空时，就继续进入循环

代码实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> ret;TreeNode* node = root;while(!st.empty() || node != nullptr){//遍历到最左边节点，边走边存储while(node){ret.push_back(node->val);st.push(node);node = node->left;}//寻找右边节点node = st.top();st.pop();node = node->right;}return ret;}
};

二叉树的中序遍历

在这里插入图片描述
94. 二叉树的中序遍历

思路分析

同前序遍历相似，我们都是需要找到最左边节点，稍有不同的就是在进行中序遍历的时候，我们只保存该路径上的栈顶元素，也就是最左节点，按照左中右的顺序进行遍历

代码实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> ret;TreeNode* node = root;while(!st.empty() || node != nullptr){while(node != nullptr){st.push(node);node = node->left;}node = st.top();ret.push_back(node->val);st.pop();node = node->right;}return ret;}
};

二叉树的后序遍历

在这里插入图片描述
145. 二叉树的后序遍历

思路分析

后序遍历较为特殊，后序遍历的遍历顺序为左右中，由于我们习惯会将根节点先入栈，所以我们考虑得到中右左的遍历结果，然后对结果进行反转，为了得到中右左的结果，除了将根节点入栈之外，由于想得到先右后左的结果，所以在入栈时要采取先左后右

代码实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> ret;stack<TreeNode*> st;if(root != nullptr)st.push(root);while(!st.empty()){TreeNode* node = st.top();ret.push_back(node->val);st.pop();if(node->left)st.push(node->left);if(node->right)st.push(node->right);}reverse(ret.begin(), ret.end());return ret;}
};