二叉树三种遍历的递归与非递归写法
目录
编辑
一，前序遍历
题目接口：
递归解法：
非递归解法：
二，中序遍历
题目接口：
递归解法：
非递归写法：
三，后序遍历
题目接口：
递归解法：
非递归解法：
一，前序遍历
题目接口：
/*** 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) {}
};递归解法：
对于这道题，相信大家都能够轻松解决掉。递归写法，非常简单：
class Solution {
public:void _preorderTraversal(TreeNode*root, vector<int>&ret){if(root == nullptr){return ;}ret.push_back(root->val);_preorderTraversal(root->left, ret);_preorderTraversal(root->right,ret);}vector<int> preorderTraversal(TreeNode* root) {vector<int>ret;_preorderTraversal(root,ret);return ret;}
};非递归解法：
但是，如果要你写出一个非递归版本的的写法呢？我们该如何写呢？步骤如下：
1. 搞一个栈，这个栈的作用是存下每一个节点。
2.定义一个cur指针，指向当前节点。然后从该节点cur开始，使用一个小循环循环遍历左子树，在将一个左子树遍历完以后也就是遍历到nullptr以后便结束循环。
3.取栈顶元素top，让cur重新指向top的右指针。然后从新的cur开始重新遍历左子树。
4.当栈为空且cur为nullptr时便可以结束大循环，返回得到的前序遍历的结果。
代码如下：
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int>ret;//存储结果的数组stack<TreeNode*>st;//栈TreeNode*cur = root;while(!st.empty()||cur)//循环结束条件，必须在两者都是nullptr的情况下才能结束循环。{while(cur){ret.push_back(cur->val);st.push(cur);cur = cur->left;}TreeNode* top = st.top();st.pop();cur = top->right;//指向右节点，遍历右树。}return ret;}
};总结，这里的关键一步便是遍历每一个节点的左树。然后将每一个节点用栈记录下来。这里为什么要使用栈呢？这是利用了栈后进先出的特点！！！由于在电脑上画图比较麻烦，所以大家可以自己根据这个代码画图模拟一下。
二，中序遍历
题目接口：
/*** 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) {}
};递归解法：
使用递归解法任仍然是简单的，也就是按照顺序左子树->根->右子树的顺序来递归遍历这棵二叉树。代码如下：
class Solution {
public:void _inorderTraversal(TreeNode*root, vector<int>&in){if(root == nullptr){return;}_inorderTraversal(root->left,in);in.push_back(root->val);_inorderTraversal(root->right,in);}vector<int> inorderTraversal(TreeNode* root) {vector<int>in;_inorderTraversal(root,in);return in;}
};非递归写法：
有了上面的前序遍历的非递归写法的思想以后，中序遍历的非递归写法就好写很多了。我们只需要在前序遍历的非递归写法上改一下根节点插入到in数组中的顺序便可以了。代码如下：
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int>ret;//存储结果的数组stack<TreeNode*>st;//栈TreeNode*cur = root;while(!st.empty()||cur)//循环结束条件，必须在两者都是nullptr的情况下才能结束循环。{while(cur)//这个循环只往栈st里面插入插入节点的指针而不往ret里面插入值{st.push(cur);cur = cur->left;}TreeNode* top = st.top();ret.push_back(top->val);//在这里才插入值st.pop();cur = top->right;//指向右节点，遍历右树。}return ret;}
};三，后序遍历
题目接口：
/*** 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) {}
};递归解法：
这道题的递归解法仍然很简单，就是按照左子树->右子树->根的顺序遍历这棵二叉树。递归代码如下：
class Solution {
public:void _postorderTraversal(TreeNode*root,vector<int>&ret){if(root == nullptr){return;}_postorderTraversal(root->left,ret);_postorderTraversal(root->right,ret);ret.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int>ret;_postorderTraversal(root,ret);return ret;}
};非递归解法：
这道题难就难在非递归解法的代码我们该如何去写呢？难就难在这里了。首先我们也都知道，后序布遍历的遍历顺序是：左子树->右子树->根。所以我们仍然要先访问左子树。我们仍然要先访问左，先把所有的左节点插入到栈里面。这一步其实和前面的中序遍历与前序遍历的思路是一样的，但是在后序遍历里面是否能够访问当前节点是要做判断的：当前节点必须在右节点被访问以后才能访问。
代码如下：
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*>st;vector<int>ret;TreeNode*cur = root;TreeNode*prev = nullptr;//记录前面访问了那一个节点while(!st.empty()||cur){while(cur)//只插入不访问{st.push(cur);cur = cur->left;}TreeNode* top = st.top();//找到最后一个插入栈的节点if(prev == top->right)//如果这个节点的右节点已经被访问过来，这个节点便是可以访问的{prev = top;//更新prevret.push_back(top->val);st.pop();}else//如果这个节点的右节点没有被访问过，便先访问右节点（右树）{cur = top->right;prev = cur;//更新prev}}return ret;}
};