本文主要是介绍二叉树的构建（已知两个遍历结果，来构建二叉树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、从前序与中序遍历构建二叉树
方法一：再构建两个数组，进行存储分割的左右子树
方法二：哈希映射
二、从中序和后序遍历构造二叉树
一、从前序与中序遍历构建二叉树
假如有这样一棵二叉树，它的前序遍历为1 2 4 5 3 6 ，中序遍历为 4 2 5 1 6 3
图文分析：
根节点为前序遍历的第一个节点
然后通过前序遍历得到的根节点以及形成的中序遍历结构进行左右子树划分
代码演示：
方法一：再构建两个数组，进行存储分割的左右子树
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if (preorder.size() == 0) return NULL;int pos = 0, n = preorder.size();while (inorder[pos] != preorder[0])pos += 1; //找到中序遍历中的根节点位置TreeNode* root = new TreeNode(preorder[0]);vector<int> preArr;// 存储前序遍历的结果vector<int> inArr; // 存储中序遍历的结果//获得根节点的左子树for (int i = 1; i <= pos; i++) preArr.push_back(preorder[i]); //前序遍历左子树的结果for (int i = 0; i <= pos; i++) inArr.push_back(inorder[i]); //中序遍历左子树的结果root->left = buildTree(preArr, inArr);preArr.clear();inArr.clear();//获得根节点的右子树for (int i = pos + 1; i < n; i++) preArr.push_back(preorder[i]); //前序遍历右子树的结果for (int i = pos + 1; i < n; i++) inArr.push_back(inorder[i]); //中序遍历右子树的结果root->right = buildTree(preArr, inArr);return root;}
};方法二：哈希映射
这个方法更便于我们找到根节点所在中序遍历的位置
class Solution {
private:unordered_map<int, int> pos;public:TreeNode* dfs(const vector<int>& preorder, const vector<int>& inorder, int pl, int pr, int il, int ir) {if (pl > pr) return nullptr;// 前序遍历中的第一个节点就是根节点int k = pos[preorder[pl]]; // 在中序遍历中定位根节点// 先把根节点建立出来TreeNode* root = new TreeNode(preorder[pl]);int len = k - il;// 得到左子树中的节点数目// 递归地构造左子树，并连接到根节点// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素root->left = dfs(preorder, inorder, pl + 1, pl + len, il, k - 1);// 递归地构造右子树，并连接到根节点// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素root->right = dfs(preorder, inorder, pl + len + 1, pr, k + 1, ir);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n = preorder.size();// 构造哈希映射，帮助我们快速定位根节点for (int i = 0; i < n; ++i) {pos[inorder[i]] = i;}return dfs(preorder, inorder, 0, n - 1, 0, n - 1);}
};
二、从中序和后序遍历构造二叉树
图文演示：
假如有这样一棵二叉树，它的后序遍历为4 5 2 6 3 1 ，中序遍历为 4 2 5 1 6 3.
代码演示：哈希映射
class Solution {
public:unordered_map <int, int>pos;TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr) {if (il > ir) return NULL;int k = pos[postorder[pr]];//中序遍历确定根位置TreeNode* root = new TreeNode(postorder[pr]); //创立根节点root->left = dfs(inorder, postorder, il, k - 1, pl, pl + k - 1 - il);root->right = dfs(inorder, postorder, k + 1, ir, pl + k - il, pr - 1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n = inorder.size();for (int i = 0; i < n; i++) {pos[inorder[i]] = i;}return dfs(inorder, postorder, 0, n - 1, 0, n - 1);}
};三、根据前序和后序遍历构造二叉树
这个知前序和后序遍历构建的二叉树得到的二叉树不唯一
代码演示：（双指针法）
考虑到后序遍历的倒数第二个节点刚好为右节点。
class Solution {
public:int preIndex = 0, posIndex = 0;TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {TreeNode* root = new TreeNode(preorder[preIndex++]);if (root->val != postorder[posIndex]) root->left = constructFromPrePost(preorder, postorder);if (root->val != postorder[posIndex]) root->right = constructFromPrePost(preorder, postorder);posIndex++;return root;}
};这篇关于二叉树的构建（已知两个遍历结果，来构建二叉树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
