代码随想录day12 | [前、中、后、层]二叉树的遍历迭代法和递归法

文章目录

- 一、前后中序递归法
- 二、前后序迭代法
- 三、中序遍历迭代法
- 四、层序遍历

递归三部曲：
1️⃣ 第一步确定递归函数的返回值和参数
2️⃣第二步确定递归的终止条件
3️⃣第三步确定单层递归处理的逻辑

一、前后中序递归法

前序遍历二叉树

class Solution
{
private:
    vector<int> res;

public:
    void dfs(TreeNode *root)
    {
        if (root == nullptr)
            return;

        res.push_back(root->val);
        if (root->left)
            preorderTraversal(root->left);
        if (root->right)
            preorderTraversal(root->right);
    }
    vector<int> preorderTraversal(TreeNode *root)
    {
        dfs(root);
        return res;
    }
};

二、前后序迭代法

前序遍历二叉树
借助栈来实现。
在这里插入图片描述

按理说应该是：根左右
但是是栈的结构，所以入孩子节点的时候，先右再左。
这样方便弹出！
在这里插入图片描述

前序遍历非递归：
class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        // 迭代法
        vector<int> res;
        stack<TreeNode *> st;
        if (root == nullptr)
            return res;
        st.push(root);

        while (!st.empty())
        {
        	// 每次进入循环需要先获得栈顶元素
            TreeNode *tmp = st.top(); // 根
            st.pop();
            res.push_back(tmp->val);

            if (tmp->right)
                st.push(tmp->right); // 右
            if (tmp->left)
                st.push(tmp->left); // 左
        }
        return res;
    }
};

前序遍历改为后序遍历只需要改2行，再加一行即可。
右左换一下顺序，再逆置一下res数组即可得到我们的答案。

后序遍历非递归：
class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        // 迭代法
        vector<int> res;
        stack<TreeNode *> st;
        if (root == nullptr)
            return res;
        st.push(root);

        while (!st.empty())
        {
        	// 每次进入循环需要先获得栈顶元素
            TreeNode *tmp = st.top(); // 根
            st.pop();
            res.push_back(tmp->val);

            
            if (tmp->left)
                st.push(tmp->left); // 左
            if (tmp->right)
            	st.push(tmp->right); // 右
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

三、中序遍历迭代法

94.二叉树的中序遍历

为何中序遍历的非递归不同？

因为访问处理的顺序和遍历的顺序是不同的。
所以我们需要一个指针来帮助我们遍历二叉树，使用栈来处理节点上的元素。

// 中序遍历使用迭代法
class Solution
{
public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        // 迭代法
        vector<int> res;
        stack<TreeNode *> st;
        TreeNode *cur = root;
        while (cur != nullptr || !st.empty())
        {
            if (cur != nullptr)
            {
                st.push(cur);
                cur = cur->left; // 左
            }
            else
            {
                // cur==nullptr 那么把cur指向栈顶元素岂不是更方便迭代？
                cur = st.top();
                st.pop();
                res.push_back(cur->val); // 根
                cur = cur->right;        // 右
            }
        }
        return res;
    }
};

四、层序遍历

102.二叉树的层序遍历
要使用队列。

class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> res;
        queue<TreeNode *> q;
        if (root != nullptr)
            q.push(root);

        while (!q.empty())
        {
            int size = q.size();
            vector<int> v;
            for (int i = 0; i < size; i++)
            {
            // 每次进入循环，都需要一个迭代变量
                TreeNode *tmp = q.front();
                q.pop(); // 每次弹出的元素就是要记录到数组的元素
                v.push_back(tmp->val);
			// 将左右孩子 加入队列
                if (tmp->left)
                    q.push(tmp->left);
                if (tmp->right)
                    q.push(tmp->right);
            }
            res.push_back(v);
        }
        return res;
    }
};