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

✅作者简介：热爱后端语言的大学生，CSDN内容合伙人
✨精品专栏：C++面向对象
🔥系列专栏：算法百炼成神

🔥前言

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

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

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

题目链接：前中后序遍历

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<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); 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

重要注释：

• 先、中、后序遍历的区别乍一看就是访问结点的顺序不同，但是如果去分析递归你会发现：
  • 先序遍历：访问到一个结点后，先将值插入数组，然后往左右子树递归，不为空就插入数据，为空就停止递归。
  • 中序遍历：一直往根结点的左子树递推，最先插入数据的一定是二叉树最左的一个结点，然后是根结点、右结点。
  • 后序遍历：与中序类似，区别是插入最左边结点后，先处理右子树在处理根结点。
• 先序最好理解，像是一步步的顺序进行；而中序和后序都要先递推到最左的子树然后再回溯。

2、AB17 从中序与后序遍历序列构造二叉树

利用了 无序 的哈希 map容器，解法巧妙，快来围观！

题目链接：构造二叉树

2.1、解题思路

刚看到题目不要慌，我们知道后序遍历的步骤是：左、右、根，说明后序序列的最后一个元素就是二叉树的根结点。

而中序遍历的步骤是：左、根、右，那么我们只要知道根结点在中序序列的位置就可以确定构建左右子树的范围了：最左与根结点位置之间用来构造左子树，根结点与最右用来构建右子树。

怎么确定根结点位置呢？那就要借助 unordered_map 容器：

• 这个容器底层是二叉树实现，无自动排序，可去重
• 根据中序的值来从零存放下标，这样做就可以根据值来找位置了

注意递归结束的条件：左边界大于右边界，不难想到左右边界相等时的情况是构建了边界结点。

2.2、代码实现及注释

本题源码：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param inorder int整型vector 中序遍历序列
     * @param postorder int整型vector 后序遍历序列
     * @return TreeNode类
     */
    TreeNode* helper(int in_left,int in_right,vector<int>& inorder,vector<int>& postorder){
        if(in_left>in_right){
            return nullptr;
        }
        // 选择 post_idx 位置的元素作为当前子树根结点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);
        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];
        // 下标减一
        post_idx--;
        // 构造右子树
        root->right=helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left=helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始，是先序根结点
        post_idx = (int)postorder.size()-1;
        // 建立 map集合(值，键) 相反的
        int idx=0;
        for(auto &val : inorder){
            idx_map[val] = idx++;
        }
        return helper(0, post_idx, inorder, postorder);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

重要注释：

• 注意结构体 struct 部分，题目给出了有参构造函数：通过构造方法创建结点默认无左右子树
• 默认给出的是 buildTree 函数，带有中序和后序的动态数组：
  • post_idx 初始代表的是后序序列最后一个元素的下标，其实也是根结点值的下标
  • for循环这块构建了一个键值对，键对应中序序列的值，而值对应着中序序列的下标
    • 这样可以传入根结点的值，从而找到根结点在中序序列的位置，划分子树的递归范围
  • 接下里就是对helper函数的调用
• helper是用来辅助的函数：
  • 先给出递归结束的条件：左边界大于右边界
  • post_idx减一后先进行右子树的递归是有东西在里面的：
    • 后序步骤是左、右、根，因此后序序列的倒数第二个下标对应的就是二叉树的右子树
  • 每一次递推都会出现左右子树的构建，直到边界不允许时开始回溯，大家可以根据示例2给出的中后序列结合代码去自己 “调试” 递归算法，你会发现构建的顺序实际上是：1、3、5、4、2

---

本次分享的两道二叉树经典题目到此结束了，如果第一道属于开胃菜，那么第二道就是正餐了。最后浅谈一下递归的知识：

递归 可分为 递推 和归溯(回溯)，前者是不断调用子函数直到无法在调用，后者是从最后一个可调用子函数中返回其结果，然后不断的往前返回，最终回溯到主递归的函数，得出最终结果。

不可否认的是二叉树类问题，使用递归解决真的很方便，或许这就是递归的魅力吧！