设计网站页面步骤,谈谈设计和建设网站体会,湖北 网站备案,网络宣传平台有哪些文章目录 二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历 正文开始前给大家推荐个网站#xff0c;前些天发现了一个巨牛的
人工智能学习网站#xff0c;
通俗易懂#xff0c;风趣幽默#xff0c;忍不住分享一下给大家。
点击跳转到网站。 二叉树的前序遍历 用递归实… 文章目录 二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历 正文开始前给大家推荐个网站前些天发现了一个巨牛的
人工智能学习网站
通俗易懂风趣幽默忍不住分享一下给大家。
点击跳转到网站。 二叉树的前序遍历 用递归实现前序遍历非常简单但是用非递归怎么实现呢 比如说这样一棵树前序遍历是先访问根再访问左子树、右子树。 但是我们要实现非递归所以我们肯定要记录每个节点只有当这个节点不然我们没办法回来访问右子树所以我们可以用一个栈然后一直找到最左边的节点在把路上节点都push进栈。然后在访问右子树节点。 我们可以把前序遍历分为这样几个部分我们每次取一个栈里面的元素就代表我们已经访问过它的根和左子树了只需要访问它的右子树就可以了所以我们去到这个节点后直接pop掉就可以了。只不过我们在找最左边的节点的时候先把这个接点给访问了就可以了。
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint v;//root为空并且栈为空就结束while(root||st.size()){while(root){v.push_back(root-val);st.push(root);root root-left;}root st.top()-right;st.pop();}return v;}
};二叉树的中序遍历 同样我们还是给这样一颗树中序遍历是要遍历左子树、根、右子树以这样的次序来遍历。我们可以使用前序遍历的思路只不过我们先不访问根我们先找到最左边的节点然后在访问右子树之前把根给访问了就可以了。
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint v;TreeNode* cur root;while(cur||!st.empty()){while(cur){st.push(cur);cur cur-left;}cur st.top();st.pop();v.push_back(cur-val);cur cur-right;}return v;}
};二叉树的后序遍历 还是这样一棵树后序遍历是以左子树、右子树、根这样的次序来进行遍历。我们会发现后序遍历用前面两个的思路好像并不能够完成因为我们访问了右子树会发现根没法访问了而且我们没法先访问根我们要先访问它的左子树和右子树然后才能访问根这样前面的思路就用不了了。
但是我们可以用一个指针来记录上一个访问的节点但是我们怎么知道这个节点的右子树访问过没有呢
我们会发现如果当前节点的右子树记录的上一个节点的指针时就说明这个颗树的左右子树被访问完了可以访问根了或者它的右子树为空也说明可以访问根了只不过我们在访问的时候要更新一下prev指针如果不是这两种情况就说明右子树存在我们需要访问右子树直接让当前节点指向它的右孩子就可以了。
ps每次更新完成后要把cur置空防止死循环。
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint v;TreeNode* cur root;TreeNode* prev nullptr;while(cur||!st.empty()){while(cur){st.push(cur);cur cur-left;}cur st.top();if(cur-rightnullptr||cur-rightprev){v.push_back(cur-val);st.pop();prev cur;cur nullptr;}else{cur cur-right;}}return v;}
};那么今天的分享就到这里了有什么不懂得可以私信博主或者添加博主的微信欢迎交流。
