1.LeetCode：654. 最大二叉树

原题链接

        给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

        创建一个根节点，其值为 nums 中的最大值。

        递归地在最大值 左边 的 子数组前缀上 构建左子树。

        递归地在最大值 右边 的 子数组后缀上 构建右子树。

        返回 nums 构建的 最大二叉树 。

        示例 1：

        输入：nums = [3,2,1,6,0,5]

        输出：[6,3,5,null,2,0,null,null,1]

        示例 2：

        输入：nums = [3,2,1]

        输出：[3,null,2,null,1]

        提示：

        1 <= nums.length <= 1000

        0 <= nums[i] <= 1000

        nums 中的所有整数 互不相同

        根据题目的算法我们直接递归构造，每次先找到当前区间的最大值，然后递归构造左右子树。

class Solution {
public:
    TreeNode* dfs(vector<int> &nums,int l,int r)
    {
        if(l>r)
        return NULL;
        int maxindex=l;
        for(int i=l;i<=r;i++)
        maxindex=nums[i]>=nums[maxindex]?i:maxindex;
        TreeNode* root=new TreeNode();
        root->left=dfs(nums,l,maxindex-1);
        root->right=dfs(nums,maxindex+1,r);
        root->val=nums[maxindex];
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode*root=dfs(nums,0,nums.size()-1);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.LeetCode:889. 根据前序和后序遍历构造二叉树

原题链接

        给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

        如果存在多个答案，您可以返回其中 任何 一个。

        示例 1：

        输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

        输出：[1,2,3,4,5,6,7]

        示例 2:

        输入: preorder = [1], postorder = [1]

        输出: [1]

        提示：

        1 <= preorder.length <= 30

        1 <= preorder[i] <= preorder.length

        preorder 中所有值都 不同

        postorder.length == preorder.length

        1 <= postorder[i] <= postorder.length

        postorder 中所有值都 不同

        保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

        这类题目也很常见了，比如根据前序后序构造一个二叉树，根据中序后序构造一个二叉树，他们的核心都是找到两个序列对应的部分然后以其中一个为依据进行分治构建。

        例如本题我们都知道前序序列的第一个一定是根结点，后序序列的最后一个一定是根节点，把这两个点在他们的序列中删去我们就得到了他们的左右子树序列。而前序序列为根-左-右，后序序列为左-右-根。那么这样就简单了，删去两个头结点后，前序序列和后序序列的前半部分均为左子树，后半部分均为右子树。我们利用两个标记premask,postmaks不断遍历两个序列并将他们的数字利用按位或累计，当相等的时候就代表该子树寻找完毕，进行递归构建。

class Solution {
    TreeNode* dfs(vector<int>& preorder,vector<int>&postorder,int prel,int prer,int postl,int postr)
    {
        if(prel>prer){
            return nullptr;
        }
        TreeNode* cur=new TreeNode(preorder[prel]);
        if(prel==prer){
            return cur;
        }
        int premask=0,postmask=0;
        int i=0;
        while(1){
            premask|=(1<<preorder[prel+1+i]);
            postmask|=(1<<postorder[postl+i]);
            if(premask==postmask){
                cur->left=dfs(preorder,postorder,prel+1,prel+1+i,postl,postl+i);
                cur->right=dfs(preorder,postorder,prel+1+i+1,prer,postl+i+1,postr);
                return cur;
            }
            ++i;
        }
        return nullptr;
    }
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        return dfs(preorder,postorder,0,preorder.size()-1,0,postorder.size()-1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3.LeetCode:1569. 将子数组重新排序得到同一个二叉查找树的方案数

原题链接

        给你一个数组 nums 表示 1 到 n 的一个排列。我们按照元素在 nums 中的顺序依次插入一个初始为空的二叉查找树（BST）。请你统计将 nums 重新排序后，统计满足如下条件的方案数：重排后得到的二叉查找树与 nums 原本数字顺序得到的二叉查找树相同。

        比方说，给你 nums = [2,1,3]，我们得到一棵 2 为根，1 为左孩子，3 为右孩子的树。数组 [2,3,1] 也能得到相同的 BST，但 [3,2,1] 会得到一棵不同的 BST 。

        请你返回重排 nums 后，与原数组 nums 得到相同二叉查找树的方案数。
由于答案可能会很大，请将结果对 10^9 + 7 取余数。

        示例 1：

        输入：nums = [2,1,3]

        输出：1

        示例 2：

        输入：nums = [3,4,5,1,2]

        输出：5

        示例 3：

        输入：nums = [1,2,3]

        输出：0

        示例 4：

        输入：nums = [3,1,2,5,4,6]

        输出：19

        示例 5：

        输入：nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]

        输出：216212978

        提示：

        1 <= nums.length <= 1000

        1 <= nums[i] <= nums.length

        nums 中所有数 互不相同 。

        做本题之前我们需要熟悉bst的结构和构建顺序。

        对于给定的数组我们先将他构造成一个bst（本题跟第一题不同，这里直接按照数字顺序进行构建），然后我们来思考如何求出方案数。在我们构造bst的时候就已经感受到了对于比根节点小的数字他总要前往左子树，对于比根节点大的数字总要前往右子树。

        既然是这样我们吧他们分成两组，大于根结点的数字和小于根节点的数字。在不改变这两组数字组内的相对顺序的情况下我们随意变换这两组数字的顺序，会发现最终构造出来的二叉树是一样的。比如 [3,4,5,1,2]，3为根，4、5大于3， 1、2小于3。但是如果我们把插入顺序变为3，4，1，2，5或者3，1，2，4，5亦或者3，4，1，5，2最终构造出来的bst都是相同的一颗。现在我们可能回想既然如此那么直接把这两组数字进行排列组合不就好了吗，但是这里再构造左子树的时候左子树又有他的左子树和右子树，右子树又有他的左子树和右子树。他们也拥有各自的方案数目。

        所以本题考查的还是树形DP，这里我们对于某个根节点需要先得到他左右子树的方案数然后再把他们组合。组合这里先不讲，先思考如何求出左右子树的方案数。当当前节点为空的时候我们返回1（因为组合要用乘法不能返回0），这样叶子节点的方案数就得出来了为1。这样左右子树为叶子节点的子树的方案数就是左子树方案数*右子树方案数%mod，这里显然是1。

        接下来我们要做的就是不改变小于和大于组的内部顺序而改变数字的顺序。怎么做呢？首先得到左右子树的数量（只需要得到数量不需要知道他们具体是谁）然后利用挖坑法，先选出几个坑放入小于组或者大于组，剩下的自然就是另外一组了。那么这样就需要用到组合数了，而组合数的公式我们都知道:
$C_{less+more}^{less}=C_{less+more-1}^{less-1}+C_{less+more-1}^{less}$

        这里我们可能会有疑问，既然在得到左右子树的方案数时已经把他们组合了那么又为什么返回上层还需要组合？如果你有这样的思考过程那么就说明你还是没有理解这个组合的含义，他仅仅是选取几个坑位放置当前根节点的小于组或者大于组，并没有改变组内的顺序（或者说组内的顺序在上一层已经组合完毕），这样的考虑显然是多余的。

class Solution {
    const int mod=1e9+7;
    long long c[1010][1010];
    TreeNode* insert(TreeNode* root,int val){
        if(!root){
            return new TreeNode(val);
        }
        if(val<root->val){
            root->left=insert(root->left,val);
        }else if(val>root->val){
            root->right=insert(root->right,val);
        }
        return root;
    }
    int cnt(TreeNode* root){
        if(!root){
            return 0;
        }
        return cnt(root->left)+cnt(root->right)+1;  
    }
    long long dfs(TreeNode* root){
        if(!root){
            return 1;
        }
        long long ans=dfs(root->left)*dfs(root->right)%mod;
        int lc=cnt(root->left);
        int rc=cnt(root->right);
        ans*=c[lc+rc][lc];
        ans%=mod;
        return ans;
    }
public:
    int numOfWays(vector<int>& nums) {
        TreeNode* root=nullptr;
        int n=nums.size();
        for(int i=0;i<n;++i){
            root=insert(root,nums[i]);
        }
        for(int i=0;i<=n;++i){
            for(int j=0;j<=i;++j){
                if(!j||j==i){
                    c[i][j]=1;
                }else {
                    c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
                }
            }
        }
        return dfs(root)-1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50