public int changeNumber (int num) {
        int a = -1;
        int cur = 0;
        int z = num;

        while(cur<2){
            if((z&1)==0) cur++;
            z=z>>1;
            a++;
        }
        return num|(1<<a);


    }

public int findInterval (String str) {
        char[] cs = str.toCharArray();
        if(cs.length<26) return -1;
        int[] times = new int[26];

        int left = 0;
        int right = -1;
        boolean flag = false;
        int n = cs.length;
        int curNumber = 0;
        int minRes = Integer.MAX_VALUE;

        while(right<n-1){
            if(!flag){
                right++;
                char c = cs[right];
                if(c=='?') curNumber++;
                else if (times[c-'a']>0){
                    times[c-'a']++;
                    continue;
                } else {
                    curNumber++;
                    times[c-'a']++;
                }
                if(curNumber>=26){
                    minRes=Math.min(minRes,right-left+1);
                    flag=true;
                }
                continue;
            }
            if(flag){
                char c = cs[left];
                left++;
                if(c=='?') curNumber--;
                else if (times[c-'a']==1){
                    curNumber--;
                    times[c-'a']-=1;
                } else times[c-'a']-=1;

                if(curNumber>=26){
                        minRes=Math.min(minRes,right-left+1);

                } else flag=false;


            }

        }

        while(left<n-1&&flag){
            char c = cs[left];
            left++;
            if(c=='?') curNumber--;
            else if (times[c-'a']==1){
                curNumber--;
                times[c-'a']-=1;
            } else times[c-'a']-=1;

            if(curNumber>=26){
                minRes=Math.min(minRes,right-left+1);

            } else flag=false;

        }

        return minRes==Integer.MAX_VALUE?-1:minRes;
    }

 HashMap<TreeNode, LinkedList<Integer>> map;
    int res;
    public int leafPairs (TreeNode root, int k) {
        res=0;
        map = new HashMap<>();
        dfs(root,k);
        return res;

    }

    public LinkedList<Integer> dfs(TreeNode cur,int k){
        if(cur==null) return new LinkedList<>();//长度为0
        if(cur.left==null&&cur.right==null){//叶子节点的list长度为1
            LinkedList<Integer> list = new LinkedList<>();
            list.add(1);
            return list;//List长度为1
        }
        LinkedList<Integer> list0 = dfs(cur.left,k);//代表叶子节点数,叶子节点的节点数
        LinkedList<Integer> list1 = dfs(cur.right,k);
        LinkedList<Integer> myList = new LinkedList<>();
        myList.add(0);//当前节点不是叶子节点.

        //left.get(a)*right.get(b) where k = a+b+2;
        for(int x = 0 ; k-x-2>=0 ; x++){
            int y = k-x-2;
            int ans0 = list0.size()>x?list0.get(x):0;
            int ans1 = list1.size()>y?list1.get(y):0;
            res+=(ans0*ans1);
        }

        Iterator<Integer> itr0 = list0.iterator();
        Iterator<Integer> itr1 = list1.iterator();
        while(true){
            if(!itr0.hasNext() && !itr1.hasNext()) break;
            int c = itr0.hasNext()?itr0.next():0;
            int d = itr1.hasNext()?itr1.next():0;
            myList.add(c+d);
        }
        return myList;

    }