代码随想客
前序遍历class Solution { public: //定义一个遍历函数 void travel(TreeNode* cur,vector中序遍历& res) { if(cur==nullptr) { return ; } //前序就是中左右 res.push_back(cur->val); travel(cur->left,res); travel(cur->right,res); } vector preorderTraversal(TreeNode* root) { vector res; travel(root,res); return res; } };
class Solution { public: //定义一个遍历函数 void travel(TreeNode* cur,vector后序遍历& res) { if(cur==nullptr) { return ; } //中序就是左中右 travel(cur->left,res); res.push_back(cur->val); travel(cur->right,res); } vector preorderTraversal(TreeNode* root) { vector res; travel(root,res); return res; } };
class Solution { public: //定义一个遍历函数 void travel(TreeNode* cur,vector二叉树的迭代遍历& res) { if(cur==nullptr) { return ; } //后序就是左右中 travel(cur->left,res); travel(cur->right,res); res.push_back(cur->val); } vector preorderTraversal(TreeNode* root) { vector res; travel(root,res); return res; } };
代码随想客
前序遍历(迭代法)class Solution { public: vector中序遍历(迭代法)preorderTraversal(TreeNode* root) { stack st; vector res; if(root==nullptr) { return res; } st.push(root); while(!st.empty()) { TreeNode* node=st.top(); st.pop(); res.push_back(node->val); if(node->right) { st.push(node->right); } if(node->left) { st.push(node->left); } } return res; } };
class Solution { public: vector后序遍历(迭代法)inorderTraversal(TreeNode* root) { vector res; stack st; if(root==nullptr) { return res; } TreeNode* cur=root; while(cur!=nullptr||!st.empty()) { if(cur!=nullptr) { st.push(cur); cur=cur->left; } else { cur=st.top(); res.push_back(st.top()->val); st.pop(); cur=cur->right; } } return res; } };
class Solution { public: vector二叉树的统一迭代遍历(看不懂也要背下来)postorderTraversal(TreeNode* root) { vector res; stack st; TreeNode* node; if(root==nullptr) { return res; } st.push(root); while(!st.empty()) { node=st.top(); st.pop(); res.push_back(node->val); if(node->left) { st.push(node->left); } if(node->right) { st.push(node->right); } } reverse(res.begin(),res.end()); return res; } };
代码随想客
统一迭代遍历基本结构如下
vector前序遍历(统一迭代)res; stack st; //首先判断根节点是否为空,非空则压入st if(root!=nullptr) { st.push(root); } //然后就是主结构 while(!st.empty()) { TreeNode* node=root; if(node!=nullptr) { st.pop(); //首先先d出,避免重复 *** 作 //前序就是反过来:右左中,且每次到中就加一个nullptr //中序就是反过来:右中左,且每次到中就加一个nullptr //后序就是反过来:中右左,且每次到中就加一个nullptr } else { //这里上来就是一个pop(),d掉空指针 st.pop(); //然后把top的指针指向的值push_back进res res.push_back(st.top->val); //然后再是一个pop() st.pop(); } } //最后一个非常简单的return return res;
class Solution { public: vector中序遍历(统一迭代)inorderTraversal(TreeNode* root) { vector res; stack st; if(root!=nullptr) { st.push(root); } while(!st.empty()) { TreeNode* node=st.top(); if(node!=nullptr) { st.pop(); if(node->right) { st.push(node->right); } st.push(node); st.push(nullptr); //中节点被访问过,但是还没有处理,加入空节点作为标记 if(node->left) { st.push(node->left); } } else//只有当遇到空节点是,才将下一节点放进res { st.pop();//d掉空节点 res.push_back(st.top()->val); st.pop();//用过后把它d掉 } } return res; } };
class Solution { public: vector后序遍历(统一迭代)preorderTraversal(TreeNode* root) { vector res; stack st; if(root!=nullptr) { st.push(root); } while(!st.empty()) { TreeNode* node=st.top(); if(node!=nullptr) { st.pop(); if(node->right) { st.push(node->right);// 右 } if(node->left) { st.push(node->left);// 左 } st.push(node); // 中 st.push(nullptr); } else { st.pop(); res.push_back(st.top()->val); st.pop(); } } return res; } };
class Solution { public: vectorpostorderTraversal(TreeNode* root) { vector res; stack st; if(root!=nullptr) { st.push(root); } while(!st.empty()) { TreeNode* node=st.top(); if(node!=nullptr) { st.pop(); st.push(node);// 中 st.push(nullptr); if(node->right) { st.push(node->right);// 右 } if(node->left) { st.push(node->left);// 左 } } else { st.pop(); res.push_back(st.top()->val); st.pop(); } } return res; } };
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)