二叉树三种遍历的递归与非递归写法

目录

​编辑

一，前序遍历

题目接口：

递归解法：

非递归解法：

二，中序遍历

题目接口：

递归解法：

非递归写法：

三，后序遍历

题目接口：

递归解法：

非递归解法：

---

一，前序遍历

题目接口：

/*** 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;}
};