二叉树的递归遍历很容易写出来, 对于递归遍历则需要借助辅助栈, 并且不同的遍历次序迭代的写法也不尽相同, 这里整理一些二叉树迭代遍历的实现
二叉树的前序遍历
代码:
- class Solution {
- public:
- vector<int> preorderTraversal(TreeNode* root) {
- stack<TreeNode*> stk;
- vector<int> ans;
- if(!root) return ans;
- stk.push(root);
- while(!stk.empty()){ // 当栈为空意味着所有结点都访问完毕了
- TreeNode* u = stk.top(); stk.pop();
- ans.push_back(u->val); // 访问当前结点
- if(u->right != NULL) stk.push(u->right); // 右孩子入栈
- if(u->left != NULL) stk.push(u->left); // 左孩子入栈, 因为栈的后进先出性质, 保证当前结点的左孩子先先于右孩子访问
- }
- return ans;
- }
- };
二叉树的中序遍历:
代码:
- class Solution {
- public:
- vector<int> inorderTraversal(TreeNode* root) {
- vector<int> ans;
- stack<TreeNode*> stk;
- TreeNode* p = root;
- while(!stk.empty() || p != nullptr){
- if(p != nullptr){
- stk.push(p);
- p = p->left; // 一直向左走
- }else{ // 找到一个最左的结点
- p = stk.top(); stk.pop(); // 把这个结点弹出栈
- ans.push_back(p->val); // 访问
- p = p->right; // 然后从其右孩子出发
- }
- }
- return ans;
- }
- };
二叉树的后序遍历:
代码:
- /*
- 因为后序遍历总是先访问结点的所有孩子, 然后再访问结点自身, 所以我们用一个 boolean visit 标记结点的孩子是否都入栈, 当从栈顶弹出的结点的孩子还没访问时, 继续访问其孩子, 并标记 visit, 否则, 就可以直接访问这个结点的值. 我认为这种遍历方式在思维上是最为清晰的, 只是我们需要用一个 pair 来组织结点及其孩子访问情况.
- */
- class Solution {
- public:
- vector<int> postorderTraversal(TreeNode* root) {
- vector<int> ans;
- stack<pair<TreeNode*, bool>> s;
- if(!root) return ans;
- s.push(make_pair(root, false));
- while(!s.empty()){
- auto& node = s.top();
- bool visited = node.second;
- if(!visited){
- if(node.first->right) s.push(make_pair(node.first->right, false));
- if(node.first->left) s.push(make_pair(node.first->left, false));
- node.second = true;
- }else{
- ans.push_back(node.first->val);
- s.pop();
- }
- }
- return ans;
- }
- };
另一种后序遍历的迭代实现:
- class Solution {
- public:
- vector<int> postorderTraversal(TreeNode* root) {
- vector<int> ans;
- stack<TreeNode*> s;
- TreeNode* p = root; TreeNode* q = nullptr;
- do{
- while(p != nullptr){
- s.push(p);
- p = p->left;
- }
- q = nullptr;
- while(!s.empty()){
- p = s.top(); s.pop();
- if(p->right == q){
- ans.push_back(p->val);
- q = p;
- }else{
- s.push(p);
- p = p->right;
- break;
- }
- }
- }while(!s.empty());
- return ans;
- }
- };
来源: http://www.bubuko.com/infodetail-3415561.html