【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(上)

简介: 【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力

🔥前言

本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面试真题,面试、找工作完全可以来这里找机会。此外,网站内的编码主题多样化,调试功能可运用性强,可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗,快去注册开启算法百炼成神之路吧!


1、AB16 实现二叉树先序,中序和后序遍历

使用 递归 实现,入门的难度,可以花少点时间挑战一下


题目链接:前中后序遍历


44f2bdb945394768b584adc6c8bd7f25.png

cd0e1e231fd340d1bb164b63a3720a18.png

1.1、解题思路

从示例中的返回值可以看出,题目要求最终返回一个 二维数组,那么就利用灵活的 vector 容器来解题:


先使用递归法写好三个序列的遍历序列

然后用三个一维 vector容器分别存放前、中、后的遍历序列

最后将三个一维容器插进一个二维 vector 容器中并返回

1.2、代码实现及注释

本题源码:

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
class Solution {
  public:
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > res; // 二维动态数组 res
    vector<int> preorder, inorder, postorder; // 存放三个序列的一维数组
    vector<vector<int> > threeOrders(TreeNode* root) {
        preOrder(root);
        inOrder(root);
        postOrder(root);
        // 插入二维数组中
        res.push_back(preorder);
        res.push_back(inorder);
        res.push_back(postorder);
        return res;
    }
    // 先序遍历
    void preOrder(TreeNode* root) {
        if (!root) return;
        preorder.push_back(root->val); 
        preOrder(root->left); // 访问左子树
        preOrder(root->right); // 访问右子树
    }
    // 中序遍历
    void inOrder(TreeNode* root) {
        if (!root) return;
        inOrder(root->left); // 访问左子树
        inorder.push_back(root->val); 
        inOrder(root->right); // 访问右子树
    }
    // 后序遍历
    void postOrder(TreeNode* root) {
        if (!root) return;
        postOrder(root->left); // 访问左子树
        postOrder(root->right); // 访问右子树
        postorder.push_back(root->val); 
    }
};

重要注释:


先、中、后序遍历的区别乍一看就是访问结点的顺序不同,但是如果去分析递归你会发现:

先序遍历:访问到一个结点后,先将值插入数组,然后往左右子树递归,不为空就插入数据,为空就停止递归。

中序遍历:一直往根结点的左子树递推,最先插入数据的一定是二叉树最左的一个结点,然后是根结点、右结点。

后序遍历:与中序类似,区别是插入最左边结点后,先处理右子树在处理根结点。

先序最好理解,像是一步步的顺序进行;而中序和后序都要先递推到最左的子树然后再回溯。


目录
相关文章
|
19天前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
52 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
21天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
14 1
|
21天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
21天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
15 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
25天前
|
存储 算法
【二叉树】—— 算法题
【二叉树】—— 算法题
【二叉树】—— 算法题
|
27天前
|
机器学习/深度学习 算法 大数据
机器学习入门:梯度下降算法(下)
机器学习入门:梯度下降算法(下)
|
21天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
17 0
|
21天前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
29 0
|
27天前
|
机器学习/深度学习 算法
机器学习入门:梯度下降算法(上)
机器学习入门:梯度下降算法(上)
|
9天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。