系列文章

【英雄哥六月集训】第 01天:数组

【英雄哥六月集训】第 02天:字符串

【英雄哥六月集训】第 03天:排序

【英雄哥六月集训】第 04天:贪心

【英雄哥六月集训】第 05天: 双指针

【英雄哥六月集训】第 06天:滑动窗口

【英雄哥六月集训】第 07天:哈希

【英雄哥六月集训】第 08天:前缀和

【英雄哥六月集训】第 09天:二分查找

【英雄哥六月集训】第 10天: 位运算

【英雄哥六月集训】第 11天: 矩阵

【英雄哥六月集训】第 12天: 链表

【英雄哥六月集训】第 13天: 双向链表

【英雄哥六月集训】第 14天: 栈

【英雄哥六月集训】第 15天: 二叉树

【英雄哥六月集训】第 16天: 队列

【英雄哥六月集训】第 17天: 广度优先搜索

【英雄哥六月集训】第 18天: 树

【英雄哥六月集训】第 19天: 二叉树

【英雄哥六月集训】第 20天: 二叉搜索树

【英雄哥六月集训】第 21天: 堆(优先队列)

【英雄哥六月集训】第 22天: 有序集合

【英雄哥六月集训】第 23天: 字典树

【英雄哥六月集训】第 24天: 线段树

【英雄哥六月集训】第 25天: 树状数组

【英雄哥六月集训】第 26天: 并查集

【英雄哥六月集训】第 27天: 图

【英雄哥六月集训】第 28天: 动态规划

【英雄哥六月集训】第 29天: 分而治之

---

分而治之

在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础，如排序算法（快速排序、归并排序）、傅立叶变换（快速傅立叶变换）。

一、 最大二叉树

654. 最大二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode dfs(int[] nums,int l,int r){
        if(l>r){
            return null;
        }
        int maxidx=l;
        for(int i=l+1;i<=r;++i){
            if(nums[i]>nums[maxidx]){
                maxidx=i;
            }
        }
        TreeNode root = new TreeNode(nums[maxidx]);
        root.left = dfs(nums,l,maxidx-1);
        root.right = dfs(nums,maxidx+1,r);
        return root;
    }
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        TreeNode root = dfs(nums,0,nums.length-1);
        return root;

    }
}
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

---

二、 根据前序和后序遍历构造二叉树

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode dfs(int[] preorder,int[] postorder,int prel, int prer,int postl, int postr){
        System.out.printf("%d %d %d %d\n",prel,prer,postl,postr);
        if(prel>prer){
            return null;
        }
        TreeNode now = new TreeNode(preorder[prel]);
        
        if(prel == prer){
            return now;
        }
        int idx = m.get(preorder[prel+1]),len=idx-postl+1;
        
        now.left=dfs(preorder,postorder,prel+1,prel+len,postl,idx);
        now.right=dfs(preorder,postorder,prel+len+1,prer,idx+1,postr-1);           
        return now;
            
    
    }
        
        
    
    Map<Integer,Integer> m = new HashMap();
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for(int i=0;i<postorder.length;i++){
            m.put(postorder[i],i);
        }
        return dfs(preorder,postorder,0,preorder.length-1,0,postorder.length-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

三、 将子数组重新排序得到同一个二叉查找树的方案数

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

class Solution {
    int maxn = 1010;
    long[][] c = new long[maxn][maxn];
    long mod = 1000000007;
    TreeNode insert(TreeNode root,int val){
        if(root==null){
            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 count(TreeNode root){
        if(root == null){
            return 0;
        }
        return count(root.left)+count(root.right)+1;
    }

    long dfs(TreeNode root){
        if(root == null){
            return 1;
        }
        long ans = dfs(root.left)*dfs(root.right)%mod;
        int leftc = count(root.left);
        int rightc = count(root.right);
        int totalc = leftc+rightc;
        ans *= c[totalc][leftc];
        ans %= mod;
        return ans;
    }
    public int numOfWays(int[] nums) {
        int i,j;
        int n = nums.length;
        for(i=0;i<=n;i++){
            for(j=0;j<=i;++j){
                if(j==0||j==i){
                    c[i][j]=1;
                }
                else{
                    c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
                }
            }
        }
        TreeNode root=null;
        for(i=0;i<nums.length;++i){
            root=insert(root,nums[i]);
        }
        return (int)(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
51
52
53
54
55
56
57

总结