分治算法（用例子说明）

「这是我参与11月更文挑战的第6天，活动详情查看：2021最后一次更文挑战」

分治法思想

分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。
代表例子有快速排序和归并排序。

例题-所有可能的满二叉树

题目描述

所有可能的满二叉树
满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。
返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
答案中每个树的每个结点都必须有 node.val=0。
你可以按任何顺序返回树的最终列表。
示例：
输入：7
输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
解释：

解题思路

n=1，只需要返回一种情况，根结点即可
n=3,根结点的左右子树都需要一个节点

n>=3时候情况就复杂了
左子树节点个数可以为：1. 3. 5 ....
右子树节点个数可以为：n-1-1. n-1-3. n-1-5...
而左右子树又会有同样的问题，只不过n变得不一样
因此我们可以对左右子树分而治之
最后得到的结果组合即可

代码

/**
 * 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 {
    public List<TreeNode> allPossibleFBT(int n) {
        int i=1;
        List<TreeNode> list=new ArrayList<>();
        if(n==1)list.add(new TreeNode(0));
        while (n-1-i>0){
            List<TreeNode> ls=allPossibleFBT(i);
            List<TreeNode> rs=allPossibleFBT(n-i-1);
            for (int i1 = 0; i1 < ls.size(); i1++) {
                for (int i2 = 0; i2 < rs.size(); i2++) {
                    TreeNode treeNode=new TreeNode(0);
                    treeNode.left=ls.get(i1);
                    treeNode.right=rs.get(i2);
                    list.add(treeNode);
                }
            }
            i+=2;
        }
        return list;
    }
}
复制代码

归并排序

package com.company;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
	// write your code here
        int []arr = {4,3,2,1,121,141,1,1,31,51,321,41123,-1,-100,1423,123,-213,11,-7,7,8,-8,8,-9};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] array){ //作为函数入口，简化规则
        int[] temp=new int[array.length]; //在堆内申请一个array.length的空间，以免后续频繁申请
        sort(0,array.length-1,array,temp);
    }
    public static void sort(int left,int right,int[] array,int[] temp){//分，分开治理
        if(left<right){
            int mid=(left+right)/2;
            sort(left,mid,array,temp);
            sort(mid+1,right,array,temp);
            merge(left,right,mid,array,temp);
        }
    }

    public static void merge(int left,int right,int mid ,int[] array,int[] temp){//治，进行合并
        if(left==right)return;
        int mid1=mid+1;
        int cur=left;
        int leftbank=left;
        while (left<=mid&&mid1<=right){
            if(array[left]<array[mid1]){
                temp[cur++]=array[left];
                left++;
            }else {
                temp[cur++]=array[mid1];
                mid1++;
            }
        }
        while (left<=mid||mid1<=right){
            if(left<=mid){
                temp[cur++]=array[left++];
            }
            if(mid1<=right){
                temp[cur++]=array[mid1++];
            }
        }
        for (int i = leftbank; i <=right ; i++) {
            array[i]=temp[i];
        }
    }


}
复制代码

快速排序

package com.company;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
	// write your code here
        int []arr = {4,3,2,1,121,141,1,1,31,51,321,41123,-1,-100,1423,123,-213,11,-7,7,8,-8,8,-9,211,212,213,214,215,216,217};
        quicksort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void quicksort(int[] array){
        quicksort(array,0,array.length-1);
    }
    public static void quicksort(int[] array,int left,int right){
        if(left>=right)return;
        if(right-left==1){
            if(array[left]>array[right]){
                int temp=array[left];
                array[left]=array[right];
                array[right]=temp;
                return;
            }
        }
        int temp=left;
        int l=left+1;
        int r=right;
        while (l<=r){
            if(array[l]<=array[temp]){
                l++;
            }else if(array[r]>=array[temp]){
                r--;
            }else {
                int value=array[l];
                array[l]=array[r];
                array[r]=value;
                l++;
                r--;
            }
        }
        int value=array[r];
        array[r]=array[temp];
        array[temp]=value;
        quicksort(array,left,r-1);
        quicksort(array,r+1,right);
    }

}
复制代码