二叉树的遍历(非递归版)

文章目录

二叉树的前序遍历
二叉树的中序遍历
二叉树的后序遍历

正文开始前给大家推荐个网站，前些天发现了一个巨牛的 人工智能学习网站， 通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。

二叉树的前序遍历

用递归实现前序遍历非常简单，但是用非递归怎么实现呢？

比如说这样一棵树，前序遍历是先访问根，再访问左子树、右子树。
但是我们要实现非递归，所以我们肯定要记录每个节点，只有当这个节点，不然我们没办法回来访问右子树，所以我们可以用一个栈，然后一直找到最左边的节点，在把路上节点都push进栈。然后在访问右子树节点。

我们可以把前序遍历分为这样几个部分，我们每次取一个栈里面的元素，就代表我们已经访问过它的根和左子树了，只需要访问它的右子树就可以了，所以我们去到这个节点后直接pop掉就可以了。只不过我们在找最左边的节点的时候先把这个接点给访问了就可以了。

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> 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:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> 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:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur = root;TreeNode* prev = nullptr;while(cur||!st.empty()){while(cur){st.push(cur);cur = cur->left;}cur = st.top();if(cur->right==nullptr||cur->right==prev){v.push_back(cur->val);st.pop();prev = cur;cur = nullptr;}else{cur = cur->right;}}return v;}
};