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 idx_map; public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param inorder int整型vector 中序遍历序列 * @param postorder int整型vector 后序遍历序列 * @return TreeNode类 */ TreeNode* helper(int in_left,int in_right,vector& inorder,vector& 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& inorder, vector& 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); } }; 重要注释： 注意结构体 struct 部分，题目给出了有参构造函数：通过构造方法创建结点默认无左右子树 默认给出的是 buildTree 函数，带有中序和后序的动态数组： post_idx 初始代表的是后序序列最后一个元素的下标，其实也是根结点值的下标 for循环这块构建了一个键值对，键对应中序序列的值，而值对应着中序序列的下标 这样可以传入根结点的值，从而找到根结点在中序序列的位置，划分子树的递归范围 接下里就是对helper函数的调用 helper是用来辅助的函数： 先给出递归结束的条件：左边界大于右边界 post_idx减一后先进行右子树的递归是有东西在里面的： 后序步骤是左、右、根，因此后序序列的倒数第二个下标对应的就是二叉树的右子树 每一次递推都会出现左右子树的构建，直到边界不允许时开始回溯，大家可以根据示例2给出的中后序列结合代码去自己 “调试” 递归算法，你会发现构建的顺序实际上是：1、3、5、4、2 本次分享的两道二叉树经典题目到此结束了，如果第一道属于开胃菜，那么第二道就是正餐了。最后浅谈一下递归的知识： 递归 可分为 递推 和归溯(回溯)，前者是不断调用子函数直到无法在调用，后者是从最后一个可调用子函数中返回其结果，然后不断的往前返回，最终回溯到主递归的函数，得出最终结果。 不可否认的是二叉树类问题，使用递归解决真的很方便，或许这就是递归的魅力吧！