二叉树的构建（已知两个遍历结果，来构建二叉树）
一、从前序与中序遍历构建二叉树假如有这样一棵二叉树，它的前序遍历为1 2 4 5 3 6 ，中序遍历为 4 2 5 1 6 3
图文分析：
根节点为前序遍历的第一个节点
然后通过前序遍历得到的根节点以及形成的中序遍历结构进行左右子树划分
代码演示：
方法一：再构建两个数组，进行存储分割的左右子树代码语言：javascript复制class Solution {
public:
TreeNode* buildTree(vector
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
vector
//获得根节点的左子树
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;
}
};方法二：哈希映射这个方法更便于我们找到根节点所在中序遍历的位置
代码语言：javascript复制class Solution {
private:
unordered_map
public:
TreeNode* dfs(const vector
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 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.
代码演示：哈希映射
代码语言：javascript复制class Solution {
public:
unordered_map
TreeNode* dfs(vector
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 n = inorder.size();
for (int i = 0; i < n; i++) {
pos[inorder[i]] = i;
}
return dfs(inorder, postorder, 0, n - 1, 0, n - 1);
}
};三、根据前序和后序遍历构造二叉树这个知前序和后序遍历构建的二叉树得到的二叉树不唯一
代码演示：（双指针法）
考虑到后序遍历的倒数第二个节点刚好为右节点。
代码语言：javascript复制class Solution {
public:
int preIndex = 0, posIndex = 0;
TreeNode* constructFromPrePost(vector
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;
}
};