将子数组重新排序得到同一个二叉搜索树的方案数

将子数组重新排序得到同一个二叉搜索树的方案数

class Solution {

    int MOD=1000000007;
    long[][] c;
    public void init(int n){
        c=new long[n][n];
        c[0][0]=1;
        for(int i=1;i<n;i++){
            c[i][0]=1;
            for(int j=1;j<n;j++){
                c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
            }
        }
    }

    public int numOfWays(int[] nums){

        int n=nums.length;
        init(n);//预处理所有的组合数
        if(n==1){
            return 0;
        }

        //根节点
        TreeNode root=new TreeNode(nums[0]);
        //对于之后的所有节点添加树
        for(int i=1;i<nums.length;i++){
            insert(root,nums[i]);
        }
        dfs(root);
        return (root.ans-1+MOD)%MOD;
    }
    public void dfs(TreeNode root){
        if(root==null){
            return;
        }
        //递归左右子树
        dfs(root.left);
        dfs(root.right);
        //如果左子树不为非空，获取左子树的节点数
        int lsize=root.left==null? 0:root.left.size;
        int rsize=root.right==null? 0:root.right.size;
        //对应的方案数
        int lans=root.left==null? 1:root.left.ans;
        int rans=root.right==null? 1:root.right.ans;

        root.ans=(int)(c[lsize+rsize][lsize]%MOD*lans%MOD*rans%MOD);

    }


    public void insert(TreeNode root,int value){//二叉搜索树添加一个节点
        //对于根节点
        TreeNode cur=root;
        while(true){
            //将当前节点字数节点加一
            ++cur.size;//将添加的过程的路径上的所有的节点都加上1
            if(value<cur.value){
                if(cur.left==null){
                    cur.left=new TreeNode(value);
                    return;
                }
                cur=cur.left;
            }else{
                if(cur.right==null){
                    cur.right=new TreeNode(value);
                    return;
                }
                cur=cur.right;
            }
        }
    }

}
class TreeNode{
    TreeNode left;
    TreeNode right;
    int value;
    int size;
    int ans;
    public TreeNode(int value){
        this.value=value;
        this.size=1;
        this.ans=0;
    }

}

二叉树的最长交错路径

二叉树最长交错路径

class Solution {
    int ans=Integer.MIN_VALUE;
    public int longestZigZag(TreeNode root) {
        int[] res=dfs(root);
        //最终结果有可能是中间节点
        // return ans-1;
        return ans;
    }
    public int[] dfs(TreeNode root){//当前子树最长交错路径 
        if(root==null){
            return new int[]{-1,-1};
        }

        int[] left=dfs(root.left);
        int[] right=dfs(root.right);

        int[] res=new int[2];

        res[0]=1+left[1];
        res[1]=1+right[0];
        ans=Math.max(ans,Math.max(res[0],res[1]));
        return res;
    }
}

树上信息统计 好节点对的数量

好节点对的数量

/**
 * 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 int countPairs(TreeNode root, int distance) {
        //通过递归的方式统计信息
        node res=dfs(root,distance);
        return res.count;
    }
    public node dfs(TreeNode root,int distance){
        int[] dist=new int[distance+1];
        //如果当前节点是叶结点
        if(root.left==null&&root.right==null){
            dist[0]=1;
            return new node(dist,0);   
        }
        node left=null;node right=null;
        if(root.left!=null){
           left=dfs(root.left,distance);    
        }
        if(root.right!=null){
            right=dfs(root.right,distance);
        }

        for(int i=1;i<=distance;i++){
            if(left!=null){
                dist[i]+=left.dist[i-1];    
            }
            if(right!=null){
                dist[i]+=right.dist[i-1];   
            }
        }

        int cnt=0;
        for(int i=0;i<distance;i++){
            for(int j=0;j+i+2<=distance;j++){
                if(left!=null&&right!=null){
                    cnt+=left.dist[i]*right.dist[j];   
                }
            }
        }
        if(left!=null){
            cnt+=left.count;
        }
        if(right!=null){
            cnt+=right.count;
        }
        return new node(dist,cnt);
    }
}
//定义需要打包进行统计的节点
class node{
    int[] dist;//表示dist[i]表示离当前节点距离为i的节点数量
    int count;
    public node(int[] dist,int count){
        this.dist=dist;
        this.count=count;
    }
}