二叉树的中序＆后序遍历——非递归版本

二叉树的中序＆后序遍历——非递归版本

引用

CSDN

1.

https://m.blog.csdn.net/2301_80689220/article/details/142718189

二叉树的遍历是数据结构中的一个重要知识点，其中中序遍历和后序遍历是两种常见的遍历方式。本文将详细介绍这两种遍历方式的非递归实现方法，帮助读者更好地理解二叉树的遍历过程。

1.题目解析

题目来源：二叉树的中序遍历——力扣
测试用例
题目来源：二叉树的后序遍历——力扣
测试用例

2.算法原理

中序遍历
中序遍历：左子树->根节点->右子树
与之前前序遍历的思路基本相同，不过需要注意的是中序变量需要在遍历完左子树后才可以访问根节点，也就是首先将左子树入栈，入栈完成后取出栈顶结点再访问该节点，这样就可以达到先访问左子树再访问根节点再访问右子树的效果

后序遍历
后序遍历：左子树->右子树->根节点
后序遍历属于三个遍历中最难的一种，因为我们需要先遍历左子树再遍历右子树后才能访问根节点，这并不是简单的将前序遍历逆置就可以得到的，首先我们有以下的困难：
1. 当访问一个节点首先将其左子树入栈后如何将其右子树入栈后再访问根节点
2.如何判断是否需要访问一个节点的右子树才能避免重复访问
3.如何控制入栈的顺序

解决方法：
1.首先我们从一棵树的根节点开始，不断向栈内插入左节点直到左边无可插入元素，此时处理栈顶元素，我们首先要判断此元素是否有右子树，有则需要入栈，反之没有则访问该节点的上一个级节点，这里判断的方法是创建一个prev保留待判断节点的栈内上一个元素，如果该元素是待判断元素的右节点则代表待判断元素的左右子树均已遍历，直接访问该节点即可
2.如果prev不是待判断元素的上一个节点则表示此时待判断节点的右子树还没有遍历，需要访问其右子树，所以将栈顶元素的右节点放入循环即可

3.实战代码

中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            //只入栈根节点而不访问
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();
            //在左子树访问完毕之后再访问根节点
            //以达到左子树->根节点->右子树的顺序
            v.push_back(top->val);
            cur = top->right;
        }
        return v;
    }
};  

后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        TreeNode* prev = nullptr;
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            //首先判断栈顶结点右子树是否为空或者之前已经访问过该节点的右子树
            //如果是则直接入到v中后在栈中删除该元素，并且将该节点更新为prev节点
            if(top->right == nullptr || top->right == prev)
            {
                v.push_back(top->val);
                st.pop();
                prev = top;
            }
            //如果没有访问过说明只是访问了之前节点的左子树
            //需要先访问右子树再访问该节点
            else
            {
                cur = top->right;
            }
        }
        return v;
    }
};