点击刷新
参考leetcode题解区@Paulking大神的模版，可以使用一个模版掌握三种遍历的非递归写法，很棒，
感谢? 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/liang-ta-lai-liao-ta-dai-zhao-san-xiong-di-lai-lia/
思路：
1. 递归的本质就是压栈，了解递归本质后就完全可以按照递归的思路来迭代。
2. 怎么压，压什么？压的当然是待执行的内容，最后执行的语句最先进栈，所以进栈顺序就决定了前中后序。
我们需要一个标志区分每个递归调用栈，这里使用nullptr来表示。具体直接看注释，可以参考文章最后“和递归写法的对比”。先序遍历看懂了，中序和后序也就秒懂。
先序遍历
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; //保存结果 stack<TreeNode*> call; //调用栈 if(root!=nullptr) call.push(root); //首先介入root节点 while(!call.empty()){ TreeNode *t = call.top(); call.pop(); //访问过的节点弹出 if(t!=nullptr){ if(t->right) call.push(t->right); //右节点先压栈，最后处理 if(t->left) call.push(t->left); call.push(t); //当前节点重新压栈（留着以后处理），因为先序遍历所以最后压栈 call.push(nullptr); //在当前节点之前加入一个空节点表示已经访问过了 }else{ //空节点表示之前已经访问过了，现在需要处理除了递归之外的内容 res.push_back(call.top()->val); //call.top()是nullptr之前压栈的一个节点，也就是上面call.push(t)中的那个t call.pop(); //处理完了，第二次弹出节点（彻底从栈中移除） } } return res; } };
后序遍历
你没看错，只有注释部分改变了顺序，父>右>左。
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> call; if(root!=nullptr) call.push(root); while(!call.empty()){ TreeNode *t = call.top(); call.pop(); if(t!=nullptr){ call.push(t); //在右节点之前重新插入该节点，以便在最后处理（访问值） call.push(nullptr); //nullptr跟随t插入，标识已经访问过，还没有被处理 if(t->right) call.push(t->right); if(t->left) call.push(t->left); }else{ res.push_back(call.top()->val); call.pop(); } } return res; } };
中序遍历
你没看错，只有注释部分改变了顺序，右>父>左。其他和前序遍历“一 模 一 样”
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> call; if(root!=nullptr) call.push(root); while(!call.empty()){ TreeNode *t = call.top(); call.pop(); if(t!=nullptr){ if(t->right) call.push(t->right); call.push(t); //在左节点之前重新插入该节点，以便在左节点之后处理（访问值） call.push(nullptr); //nullptr跟随t插入，标识已经访问过，还没有被处理 if(t->left) call.push(t->left); }else{ res.push_back(call.top()->val); call.pop(); } } return res; } };
对比中序遍历的递归写法
void dfs(t){ //进入函数表示“访问过”，将t从栈中弹出 dfs(t->left); //因为要访问t->left, 所以我先把函数中下面的信息都存到栈里。 //依次call.push(t->right), call.push(t)【t第二次入栈】, call.push(nullptr)【标识t二次入栈】, call.push(t->left)。 //此时t并没有被处理（卖萌）。栈顶是t->left, 所以现在进入t->left的递归中。 //res.push_back(t->val) t.卖萌(); //t->left 处理完了，t->left被彻底弹出栈。 //此时栈顶是nullptr, 表示t是已经访问过的。那么我现在需要真正的处理t了（即，执行卖萌操作）。 //卖萌结束后，t 就被彻底弹出栈了。 dfs(t->right); }
总结：这里最巧妙地的是使用了一种nullptr表示栈递归调用结束的方法，nullptr在t之后压栈，那么在nullptr出栈的时候我们就知道下一个出栈节点t肯定是被第二次放入栈的。对于第二次放入栈 的节点，我们就可以对它进行处理（比如打印数值，加入结果列表，卖萌等等）。另外，这里“访问过”的意思是第一次出栈，把子节点压栈了。
© 著作权归作者所有
举报
相关热门文章
发表评论
0/200
