前序-中序-后序-遍历构建二叉树

• 通过-二叉树的两种遍历方式构建二叉树
• 构建的算法框架：
• • 1·前序遍历&&中序遍历结合
  • 2·后续遍历&&中序遍历结合
  • 3·前序遍历&&与后续遍历结合
  • 4·练习题目
• 5·对应C++代码
• • [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
  • [106. 从中序与后序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
  • [654. 最大二叉树](https://leetcode.cn/problems/maximum-binary-tree/)
  • [889. 根据前序和后序遍历构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)

1. 前序遍历：根结点-左子树-右子树
2. 中序遍历：左子树-根结点-右子树
3. 后续遍历：左子树-右子树-根结点

先确定二叉树的根结点–然后找到其在另外一种遍历方式当中的数组下标，然后确定左子树的偏移量，构建根结点，递归勾构建左右子树

1. 前序遍历的第一个值就为根结点
2. 在中序遍历中找到对应的根结点下标
3. 计算其从根结点到-左子树的偏移量
4. 构建根结点
5. 递归构建-左右树

1. 后续遍历的最后一个值就为根结点
2. 在中序遍历中找到对应的根结点下标
3. 计算其从根结点到-左子树的偏移量
4. 构建根结点
5. 递归构建-左右树

1. 前序遍历的第一个值/后续遍历的最后一个值–为根结点，随机取一个值
2. 前序遍历根结点+1的值为左子树的值–在后续遍历中找到对应的下标
3. 确定左子树的个数
4. 构建根接结点
5. 递归构建-左右子树

class Solution {
    //函数定义，用preorder 和inorder构造二叉树
public:
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        //先序遍历--先遍历根结点-再遍历左子树，最后遍历右子树
        //中序遍历，先遍历左子树-再遍历根结点，最后遍历右子树
        
        return Build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
    TreeNode *Build(const vector&preorder,int prestart,int preend,const vector&inorder,int instart,int inend){
        if(prestart>preend){
            return NULL;
        }
        //根结点为先序遍历的第一个元素
        int rootval=preorder[prestart];
        //再中序遍历中找到索引的值
        int index=-1;
        for(int i=0;i<=inend;i++){
            if(inorder[i]==rootval){
                index=i;
                break;
            }
        }
        //第一个结点为根结点--所以按照其第一个根结点来构建
        TreeNode *root=new TreeNode(preorder[prestart]);
        int leftsize=index-instart;
        root->left=Build(preorder,prestart+1,prestart+leftsize,inorder,instart,index-1);
        root->right=Build(preorder,prestart+leftsize+1,preend,inorder,index+1,inend);
        return root;
    }
};

class Solution {
public:
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        
        return Build (inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
    }
    TreeNode *Build(const vector&inorder,int inStart,int inEnd,const vector&postorder,int poStart,int poEnd){
        if(poStart>poEnd){
            return nullptr;
        }
        //根结点为 inorder的最后一个值
        int root_val=postorder[poEnd];
        //在中序遍历中寻找根结点的位置
        int index=-1;
        for(int i=0;i<=inEnd;i++){
            if(inorder[i]==root_val){
                index=i;
                break;
            }
        }
        //构建根结点
        TreeNode *root=new TreeNode(postorder[poEnd]);
        //root在后续遍历中对应的-数组下标关系
        int leftsize=index-inStart;
        root->left=Build(inorder,inStart,index-1,postorder,poStart,poStart+leftsize-1);
        root->right=Build(inorder,index+1,inEnd,postorder,poStart+leftsize,poEnd-1);
        return root;
    }
};

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector& nums) {
        
        if(nums.size()==0){
            return nullptr;
        }
        //左闭右闭区间
       return  b(nums,0,nums.size()-1);
    }
    TreeNode *b(vector&nums,int lo,int hi){
        int max_val=INT_MIN;;
        if(lo>hi){
            return NULL;
        }
        //找到数组中最大值得索引
        int index=-1;
        for(int i=lo;i<=hi;i++){
            if(nums[i]>max_val){
                max_val=nums[i];
                index=i;
            }
        }
        //构建最大值的树--每次以-数组所在下标去构建
        TreeNode *root=new TreeNode(nums[index]);
        //递归调用--构造左右子树
        root->left=b(nums,lo,index-1);
        root->right=b(nums,index+1,hi);
        return root;
    }
};

class Solution {
public:
    TreeNode* constructFromPrePost(vector& preorder, vector& postorder) {
        

        return Build(preorder,0,preorder.size()-1,postorder,0,postorder.size()-1);
    }
    TreeNode *Build(const vector&preorder,int preStart,int preEnd,const vector&postorder,int poStart,int posEnd){
        if(preStart>preEnd){
            return nullptr;
        }
        if(preStart==preEnd){
            return new TreeNode(preorder[preStart]);
        }
        //先确定根结点
        int root_val=preorder[preStart];
         //确定根结点的左子树
        int rootleftval=preorder[preStart+1];
        //在后续序遍历中找到-根结点对应的下标
        int index=-1;
        for(int i=0;i<=posEnd;i++){
            if(postorder[i]==rootleftval){
                index=i;
                break;;
            }
        }
        //建立根结点
        TreeNode *root =new TreeNode(preorder[preStart]);
        //左子树的元素个数
        int leftsize=index-poStart+1;
        //递归构造左右子树
        root->left=Build(preorder,preStart+1,preStart+leftsize,postorder,poStart,index);
        root->right=Build(preorder,preStart+leftsize+1,preEnd,postorder,index+1,posEnd-1);
        return root;
    }
};