首页 > 代码库 > 二叉树系列 - 二叉树的前/中/后序遍历(非递归)
二叉树系列 - 二叉树的前/中/后序遍历(非递归)
二叉树的遍历是二叉树中最最基础的部分。
这里整理二叉树不用递归实现三种顺序遍历的方式。
不用递归的话，一般需要栈来完成。当然线索二叉树(不需要栈或递归)也可以完成中序遍历，这种方式在这篇文章中已经讨论过。这里着重讨论使用栈的实现方式。
中序遍历
(1) 双while，第二个内层while是为了不断压入left child。
vector<int> inorderTraversal(TreeNode *root) { vector<int> v; if(!root) return v; TreeNode* tmp = root; stack<TreeNode* > st; while(tmp || !st.empty()){ while(tmp){ st.push(tmp); tmp = tmp -> left; } if(!st.empty()){ tmp = st.top(); st.pop(); v.push_back(tmp -> val); tmp = tmp -> right; } } return v; }
Leet Code: Binary Tree Inorder Traversal AC 8ms
更简单的去掉内层循环的写法，原理其实一样，唯一不同的就是高亮部分。
vector<int> inorderTraversal(TreeNode *root) { vector<int> v; if(!root) return v; TreeNode* tmp = root; stack<TreeNode* > st; while(tmp || !st.empty()){ if(tmp){ st.push(tmp); tmp = tmp -> left; }else{ tmp = st.top(); st.pop(); v.push_back(tmp -> val); tmp = tmp -> right; } } return v; }
Leet Code: Binary Tree Inorder Traversal AC 32ms
后序遍历
(1) 两栈实现法，一个栈st1用类似前序遍历的方式(细微的不同之处在于 left child先进栈)，将所有输出存入另一个栈st2中。最后将st2的内容挨个输出就结了。
这种方式非常好理解，因为后序遍历就是那个改动后的前序遍历的倒序输出。st2的作用只有一个：就是逆序。因此如果输出结果是存在vector里的话，把结果直接reverse也可以。
(2) 一栈实现法，这种方式需要定义一个pre指针。
这种方式也很好理解，后序就是parent比孩子后输出，那么我们只要读到parent的时候，不忙着输出parent的值，而是让其留在栈内，把左右孩子继续往栈里压。
那啥时候才能输出parent呢？当发现左右孩子已经被输出的时候，就可以输出parent 了。pre就是用来记录最近输出的结点的。
vector<int> postorderTraversal(TreeNode *root) { std::vector<int> v; if(NULL == root) return v; std::stack<TreeNode*> st; TreeNode* pre = NULL; TreeNode* cur = NULL; st.push(root); while(!st.empty()){ cur = st.top(); if((NULL == cur -> right && NULL == cur -> left) || (NULL != pre && (pre == cur -> right || pre == cur -> left))){ //For each node, there will never be such case that one child is pre, one child is not yet traversed. Because both children are printed (or it‘s NULL) before stack.top == cur. //So if one child points to pre, that means current node can also be printed. //NULL != pre is used for the edge case that only two nodes: root contains one left node. st.pop(); v.push_back(cur -> val); pre = cur; }else{ if(NULL != cur -> right) st.push(cur -> right); if(NULL != cur -> left) st.push(cur -> left); } } return v;
二叉树系列 - 二叉树的前/中/后序遍历(非递归)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。