上海嘉定网站,.net网站与php网站,网站制作哪家便宜,mixkit免费高清视频素材目录
编辑
一#xff0c;前序遍历
题目接口#xff1a;
递归解法#xff1a;
非递归解法#xff1a;
二#xff0c;中序遍历
题目接口#xff1a;
递归解法#xff1a;
非递归写法#xff1a;
三#xff0c;后序遍历
题目接口#xff1a;
递归解法前序遍历
题目接口
递归解法
非递归解法
二中序遍历
题目接口
递归解法
非递归写法
三后序遍历
题目接口
递归解法
非递归解法 一前序遍历
题目接口
/*** 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:vectorint preorderTraversal(TreeNode* root) {}
};
递归解法
对于这道题相信大家都能够轻松解决掉。递归写法非常简单
class Solution {
public:void _preorderTraversal(TreeNode*root, vectorintret){if(root nullptr){return ;}ret.push_back(root-val);_preorderTraversal(root-left, ret);_preorderTraversal(root-right,ret);}vectorint preorderTraversal(TreeNode* root) {vectorintret;_preorderTraversal(root,ret);return ret;}
};
非递归解法
但是如果要你写出一个非递归版本的的写法呢我们该如何写呢步骤如下
1. 搞一个栈这个栈的作用是存下每一个节点。
2.定义一个cur指针指向当前节点。然后从该节点cur开始使用一个小循环循环遍历左子树在将一个左子树遍历完以后也就是遍历到nullptr以后便结束循环。
3.取栈顶元素top让cur重新指向top的右指针。然后从新的cur开始重新遍历左子树。
4.当栈为空且cur为nullptr时便可以结束大循环返回得到的前序遍历的结果。
代码如下
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorintret;//存储结果的数组stackTreeNode*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:vectorint inorderTraversal(TreeNode* root) {}
};
递归解法
使用递归解法任仍然是简单的也就是按照顺序左子树-根-右子树的顺序来递归遍历这棵二叉树。代码如下
class Solution {
public:void _inorderTraversal(TreeNode*root, vectorintin){if(root nullptr){return;}_inorderTraversal(root-left,in);in.push_back(root-val);_inorderTraversal(root-right,in);}vectorint inorderTraversal(TreeNode* root) {vectorintin;_inorderTraversal(root,in);return in;}
};
非递归写法 有了上面的前序遍历的非递归写法的思想以后中序遍历的非递归写法就好写很多了。我们只需要在前序遍历的非递归写法上改一下根节点插入到in数组中的顺序便可以了。代码如下
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorintret;//存储结果的数组stackTreeNode*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:vectorint postorderTraversal(TreeNode* root) {}
};
递归解法
这道题的递归解法仍然很简单就是按照左子树-右子树-根的顺序遍历这棵二叉树。递归代码如下
class Solution {
public:void _postorderTraversal(TreeNode*root,vectorintret){if(root nullptr){return;}_postorderTraversal(root-left,ret);_postorderTraversal(root-right,ret);ret.push_back(root-val);}vectorint postorderTraversal(TreeNode* root) {vectorintret;_postorderTraversal(root,ret);return ret;}
};
非递归解法
这道题难就难在非递归解法的代码我们该如何去写呢难就难在这里了。首先我们也都知道后序布遍历的遍历顺序是左子树-右子树-根。所以我们仍然要先访问左子树。我们仍然要先访问左先把所有的左节点插入到栈里面。这一步其实和前面的中序遍历与前序遍历的思路是一样的但是在后序遍历里面是否能够访问当前节点是要做判断的当前节点必须在右节点被访问以后才能访问。
代码如下
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode*st;vectorintret;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;}
};
