在曾经的博客中，曾经记录过这样一题：

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

这是一个只需要前序就能构造二叉树的题，因为一旦遇到空，就有"#"作为返回的标志，能够立刻返回。

1. 中序+前序

                                                            

完全可以借鉴引言中的题目的逻辑：整体采用前序构造，即先构造当前节点，再用递归子函数去构建左右节点。一旦左右节点遇到空，就返回。

但是引言中题目可以通过是否等于# 来判断，我们则需要通过中序来判断。

操作方法：前序确定根，中序分割区间

                               

以上图为例：

首先，前序的第一个数据一定是整个二叉树的根（3），我们在中序中找到3，根据中序遍历的特点，3左边的数据都属于3的左子树，3右边的数据都属于3的右子树。

进入递归，左子树的区间（后文称为左区间）只有一个数据。尽管只有一个数据9，我们还是先去前序中找属于左区间的第一个数据 ， 由于前序的遍历特点，这个数据一定是左子树的根。9把整个左区间分为两个部分：新的左区间和新的右区间（两个都为空）

因为两个都为空，所以我们可以直接返回了。然后来看3的右区间，也就是15、20、7

我们在前序中去找这三个数字出现的第一个数字（20），即为右子树的根，20将右区间分为新的左区间（15）和新的右区间（7），重复上述逻辑即可。

总结：

用前序的根去分割中序对应的区间，只要中序被分割之后还有数据区间，就继续分割；如果中序被分割之后区间为空，则直接返回。

代码实现：

因为每次递归都要传入一个新的区间，所以不能在原函数上递归。

class Solution {
public:TreeNode* build(vector<int>& preorder, vector<int>& inorder,int& prei,int inbegin,int inend){if(inbegin>inend){return nullptr;}//inbegin和inend就是此轮递归我们要构建的区间,现在我们到这个区间中寻找前序对应的根int rooti = inbegin;while(rooti<=inend){//一定能在这个区间中找到if(inorder[rooti]==preorder[prei]){prei++;//前序往前走，便于下一轮递归找rootbreak;}else{rooti++;}}//rooti已经走到了根的位置，区间分为[inbegin,rooti-1] rooti [rooti+1,inend]TreeNode* root = new TreeNode(inorder[rooti]);root->left = build( preorder, inorder, prei,inbegin, rooti-1);root->right = build( preorder,inorder,prei,rooti+1, inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int prei = 0;return build(preorder, inorder,prei,0,inorder.size()-1);}
};

---

2. 中序+后序

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

                                                           

几乎是相同的逻辑。

前序是：根 左 右

后序是：左 右 根

因此，3一定是整体的根，在inorder中，3将整体分为两部分，

由后序的特点，紧邻着3的是右树，所以我们从右数开始构建（相当于倒着遍历postorder）

左边部分是9，右边部分是15,20,7，我们在右边部分找到20,20将新的右区间分为15和7........

 一样的逻辑：

class Solution {
public:TreeNode* build(vector<int>& inorder, vector<int>& postorder, int& posti,int inbegin,int inend){if(inbegin>inend){return nullptr;}int rooti = inbegin;while(rooti<=inend){if(inorder[rooti]==postorder[posti]){posti--;break;}else{rooti++;}}//找到了，分为三个区间 [inbegin,rooti-1] rooti [rooti+1,inend]TreeNode* root = new TreeNode(inorder[rooti]);root->right = build(inorder, postorder, posti,rooti+1,inend);root->left = build(inorder, postorder, posti,inbegin,rooti-1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int posti = postorder.size()-1;return build(inorder,postorder,posti,0,inorder.size()-1);}
};

还有就是注意在递归部分是先构建右子树，再构建左子树。