代码随想录 | Day25 | 二叉树：从中序与后序遍历构造二叉树&&最大二叉树
主要学习内容：
用中序和后序来构建二叉树
106.从中序与后序遍历构造二叉树
106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
解法思路：
先想想如果没有这个图的话，我们会如何把根据这两个数组把树画出来。
1.中序是左中右，后序是左右中，说明后序数组的末尾肯定是当前还没构造的部分的根结点
2.接下来再根据这个值去中序里面找，找到的话，那它的前面就是左子树，后面就是右子树
3.根据中序数组左子树结点数量，可以确定后序数组中左右的分界，这样就找到了中序和后序数组中，左子树和右子树的范围
4.也就是分别找到了左子树和右子树他们自己的中序和后序数组
5.递归左子树和右子树的中序后序数组，建立左右子树，知道整棵树构建完毕
比如下面，这张图的构造过程
1.先找到根结点3
2.3前面是左子树9，后面是右子树15,20,7
3.左子树大小为1说明，后序数组前面1个数是左子树，到末尾的根结点前是右子树15,7,20
4.左子树中序 ：9 后序：9
右子树中序 ：15 20 7 后序：15 7 20
5.递归9和9 15 20 7和15 7 20
现在我们了解了大致过程，难点在于
1.我们该如何知道构造完的根结点在哪，即我们的递归函数返回值是什么？
2.递归函数的终止条件又该是什么？
1.我们需要最后返回我们构造的二叉树，所以我们的返回值得是我们构造二叉树的根结点，也是通过函数返回值得到根节点
2.终止条件应该是后序数组为空，后序数组为空说明已经没有结点需要进行构造了、
1.函数参数和返回值
TreeNode *tra(vector<int> i, vector<int> p)
i，p对应当前构造子树的中序和后序数组，返回值TreeNode * 是我们的根结点
2.终止条件
if(p.size()==0) return nullptr;
后序数组为空
3.本层代码逻辑
这部分是最难的地方，我们需要把我们刚刚想象的过程用代码进行复刻、
1.找到当前子树的根结点，就是后序数组的最后一个值
TreeNode *t=new TreeNode(p[p.size()-1]);
2.找到中序数组中左子树和右子树的切分点，即在中序数组中找到根节点，找到根节点的下标位置以后就break
int index=0;
for(index=0;index<i.size();index++)if(i[index]==t->val)break;
3.构造左子树，要注意采用的区间是左闭右闭还是左闭右开，不管用哪种都要统一
我采用的是左闭右开，因为迭代器的begin和end是左闭右开的
我们切割左子树的中序和后序
中序就是从开始到根结点的下标值，[0,index)
后序也是[0,index)
t->left=tra(vector<int>(i.begin(),i.begin()+index),vector<int>(p.begin(),p.begin()+index));
4.构造右子树
我们切割右子树的中序和后序
中序就是从开始到根结点的下标值，[index+1,end)，end是只想末尾位置的下一位置的迭代器（可以理解为指针），index+1是因为要把根结点跳过，他不属于子树内容
后序是[index,end-1)，因为后序的左右子树直接挨着，而最后一个是根节点，我们一样不要根结点
5.返回根结点
return t;
本层逻辑完整代码：
TreeNode *t=new TreeNode(p[p.size()-1]);int index=0;for(index=0;index<i.size();index++)if(i[index]==t->val)break;t->left=tra(vector<int>(i.begin(),i.begin()+index),vector<int>(p.begin(),p.begin()+index));t->right=tra(vector<int>(i.begin()+index+1,i.end()),vector<int>(p.begin()+index,p.end()-1));return t;
完整代码：
class Solution {
public:TreeNode *tra(vector<int> i, vector<int> p){if(p.size()==0) return nullptr;TreeNode *t=new TreeNode(p[p.size()-1]);int index=0;for(index=0;index<i.size();index++)if(i[index]==t->val)break;t->left=tra(vector<int>(i.begin(),i.begin()+index),vector<int>(p.begin(),p.begin()+index));t->right=tra(vector<int>(i.begin()+index+1,i.end()),vector<int>(p.begin()+index,p.end()-1));return t;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {return tra(inorder,postorder);}
};
654.最大二叉树
654. 最大二叉树 - 力扣（LeetCode）
解法：
这没啥好说的，就和上一题一模一样，就是从后序找根节点换成找一个数组里面的最大值了。
class Solution {
public:TreeNode *tra(vector<int> nums){//终止条件if(nums.size()==0)return nullptr;//记录最大值下标和最大值int index=0,maxVal=INT_MIN;for(int i=0;i<nums.size();i++)if(nums[i]>maxVal){maxVal=nums[i];index=i;}//构建根节点TreeNode *t=new TreeNode(maxVal);//构建左子树，还是采用左闭右开t->left=tra(vector<int>(nums.begin(),nums.begin()+index));//构建右子树t->right=tra(vector<int>(nums.begin()+index+1,nums.end()));//返回根节点return t;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return tra(nums);}
};
