[数据结构与算法]递归的魅力（树篇）二

要说的是，关于递归，要去相信递归函数的作用，不要跳入递归，下面来感受下递归的魅力
有些时候 需要去处理边界，但大概框架对了，剩下的都是debug

最大二叉树 Midium

654. 最大二叉树 - 力扣（LeetCode） (leetcode-cn.com)Midium

这题思路是遍历找到数组最大元素，获取下标然后建树，左区间和又区间递归再进行建树

TreeNode* construct(vector<int>&nums,int l,int r){
    //递归的作用便是返回nums数组下标l到r的最大二叉树
        if(l>=r){
            return nullptr;
        }

        int index=-1,maxVal=INT_MIN;
        for(int i=l;i<r;++i){
            if(maxVal<nums[i]){
                index=i;
                maxVal=nums[i];
            }
        }

        TreeNode *root=new TreeNode(maxVal);

        root->left=construct(nums,l,index);
        root->right=construct(nums,index+1,r);

        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.empty()){
            return nullptr;
        }
        return construct(nums,0,nums.size());
    }

从前序与中序遍历序列构造二叉树Midium

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com)Midium

TreeNode* build(vector<int>& preorder,int preStart,int preEnd,vector<int>& inorder,int inStart,int inEnd){
    //递归作用为构造前序和中序遍历序列为参数数组的二叉树，并返回根节点
        if(preStart>preEnd){
            return nullptr;
        }

        int rootVal=preorder[preStart];

        int index=0;
        for(int i=inStart;i<=inEnd;++i){
            if(inorder[i]==rootVal){
                index=i;
                break;
            }
        }

        int leftSize=index-inStart;

        TreeNode* root=new TreeNode(rootVal);

        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;
    }                     
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()){
            return nullptr;
        }
        return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }

从中序与后序遍历序列构造二叉树Midium

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com)Midium

TreeNode* build(vector<int>& inorder,int inStart,int inEnd,vector<int>& postorder,int postStart,int postEnd){
        if(inStart>inEnd){
            return nullptr;
        }

        int rootVal=postorder[postEnd];

        int index=0;
        for(int i=inStart;i<=inEnd;++i){
            if(inorder[i]==rootVal){
                index=i;
                break;
            }
        }

        int leftSize=index-inStart;
        TreeNode *root=new TreeNode(rootVal);

        root->left=build(inorder,inStart,index-1,postorder,postStart,postStart+leftSize-1);
        root->right=build(inorder,index+1,inEnd,postorder,postStart+leftSize,postEnd-1);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return build(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
    }