题解 | #二叉树节点间的最大距离问题#

package com.wyj.ch4;

/**
 * @author： wyj
 * @describe：
 * @version：V01
 * @date： 2021/7/28- 2:49
 */
public class h4a1 {
    /*f1：传统的方法  x:代表乘法  *：代表幂次
    F(n)=F(n-1)+F(n-2) 暴力   时间复杂度O(2*N)
    * */
    public static int f1(int n){
        if(n<1){
            return 0;
        }
        if(n==1||n==2){
            return 1;
        }
        return f1(n-1)+f1(n-2);

    }


    /*f2:从左到右依次求出每一项的值，通过顺序计算求到第N项
    时间复杂度O(N)
    * */
    public static int f2(int n){
        if(n<1){
            return 0;
        }
        if(n==1||n==2){
            return 1;
        }

        int res=1;//f(i)    f(i-1)
        int pre=1;//f(i-1)  f(i-2)
        int tmp=0;
        for (int i = 3; i <=n ; i++) {
            tmp=res;
            res=res+pre;//f(i)=f(i-1)+f(i-2)
            pre=tmp;//f(i-1)
        }
        return res;

    }

    /*矩阵乘法
    时间复杂度：O(logN)
    int mod=(int) (1e9+7);
    为防止数越界，最后输出第n项对mod取模的值
    * */
    public static int f3(int n){
        int mod=(int) (1e9+7);
        if(n<1){
            return 0;
        }
        if(n==1||n==2){
            return 1;
        }
        int[][]base={{1,1},{1,0}};
        int[][]res=matrixPower(base,n-2);
//        return res[0][0]+res[1][0];
        return (res[0][0]+res[1][0])%mod;

    }

    //求矩阵m的p次方
    public static int[][] matrixPower(int [][]m,int p){
        int[][]res=new int[m.length][m[0].length];
        //先把res设为单位矩阵，相当于整数中1
        for (int i = 0; i < m.length; i++) {
            res[i][i]=1;
        }

        int[][]tmp=m;
        //求p对应的二进制
        for(;p!=0;p>>=1){
            if((p&1)!=0){
                res=mulMatrix(res,tmp);
            }
            tmp=mulMatrix(tmp,tmp);
        }

        return res;
    }

    //矩阵m1 矩阵m2相乘
    public static int[][] mulMatrix(int [][]m1,int [][]m2){
        int mod=(int) (1e9+7);
        int[][] res=new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
//                    res[i][j]=res[i][j]+m1[i][k]*m2[k][j];
                    res[i][j]=(res[i][j] + (m1[i][k]*m2[k][j])%mod)%mod;
                }
            }
        }

        return res;
    }






}