更正错误 淘宝笔试题-字典树

class Solution {
	//本题最好的方式采用字符串排序的方式

    public String largestNumber(int[] nums) {
    	if(nums.length<=0){
    		return null;
    	}
    	String[] strs = new String[nums.length];
    	for (int i = 0; i < nums.length; i++) {
			strs[i] = String.valueOf(nums[i]);
		}
    	
    	Arrays.sort(strs,new Comparator<String>() {

			@Override
			public int compare(String o1, String o2) {
				// TODO Auto-generated method stub

				//return o1.compareTo(o2);   //这是正常的排序

				String  leftRight = o1+o2;
				String  rightLeft = o2+o1;
				return  -leftRight.compareTo(rightLeft);
			}
		});
    	
    	StringBuilder sb = new StringBuilder();
    	for (String str : strs) {
    		System.out.print(str+"  ");
			sb.append(str);
		}
    	while(sb.length()>1 && sb.charAt(0)=='0'){
    		sb.deleteCharAt(0);
    	}
    	return sb.toString();
    }
}

class TreeNode{
	int val;
	int freq = 0;      //统计词频

	int MAX_SIZE = 10;
	TreeNode[] digits;
	TreeNode(int x){
		this.val = x;
		digits = new TreeNode[MAX_SIZE];   //对象默认赋值为空

	}
}

class Trie{
	TreeNode root;
	Trie(){
		root = null;   
	}
	
	public void insertOneInteger(int num){
		if(root == null){
			root = new TreeNode(-1);
		}
		TreeNode cur = root;
		int[] arr = int2Arr(num);
		for (int i = 0; i < arr.length; i++) {
			if(cur.digits[arr[i]]==null){
				cur.digits[arr[i]] = new TreeNode(arr[i]);   //不为空，则建一个节点

			}
			cur = cur.digits[arr[i]];
			if(i == arr.length-1){         //统计单词的词频

				cur.freq+=1;
			}   
		}
	}
	
	public void buildTrie(int[] nums){   //构建字典树

		for (int i = 0; i < nums.length; i++) {
			insertOneInteger(nums[i]);
		}
	}
	
	public void PreOrderTravelse(TreeNode root){   //优先遍历我们的字典树

		if(root == null){
			return;
		}else{
				System.out.print(root.val + "=="+root.freq+"  ");
			for (int i = 0; i < root.MAX_SIZE; i++) {
				PreOrderTravelse(root.digits[i]);
			}
			
		}
	}
	
	public ArrayList<ArrayList<Integer>> LevelOrderTravelse(TreeNode root){  //层序遍历我们的字典树

		ArrayList<ArrayList<Integer>> arrs = new ArrayList<>();
		if(root == null){
			return arrs;
		}
		ArrayList<Integer> arr = new ArrayList<>();
		Queue<TreeNode> que = new LinkedList<>();
		Queue<Integer> queLevel = new LinkedList<>();
		que.add(root);
		queLevel.add(0);
		int level = 0;
		while(que.size()>0){
			if(queLevel.peek()>level){   //说明进入下一层了

				arrs.add(arr);
				arr = new ArrayList<>();
				arr.add(que.peek().val);
			}else{
				arr.add(que.peek().val);
			}
			for (int i = 0; i < root.MAX_SIZE; i++) {
				if(que.peek().digits[i]!=null){
					que.add(que.peek().digits[i]);
					queLevel.add(queLevel.peek()+1); 
				}
			}
			level = queLevel.peek();
			que.poll();
			queLevel.poll();
		}
		arrs.add(arr);
		return arrs;
	}
	
	private int[] int2Arr(int num){    //将一个整数转换为数组

		int[] arr = new int[intLen(num)]; 
		int count = intLen(num)-1;
		while(num>0){
			arr[count] = num%10;
			num /= 10;
			count--;
		}
		return arr;
	}
	private int intLen(int num){      //求一个整数的长度

		if(num<0){
			return 0;
		}
		if(num == 0){
			return 1;
		}
		int count = 0;
		while(num>0){
			num/=10;
			count++;
		}
		return count;
	}

	public int depth(TreeNode root){
		return LevelOrderTravelse(root).size();
	} 
	
	public ArrayList<String> TrieTreePath(TreeNode root){   //取出我们词  遍历

		ArrayList<String> paths = new ArrayList<>();
		if(root == null){  //这一层是根节点

			return paths;
		}
		helper(root,"",paths);
		return paths;
	}
	
	private void helper(TreeNode root,String path,ArrayList<String> paths){
		
		boolean flag = true;
		for (int i = 0; i < root.MAX_SIZE; i++){
			flag  = (flag&& (root.digits[i] == null));
		}
		if(flag == true){   //说明到了叶子节点

			paths.add(path+"|"+root.freq);
			return;
		}       
		
		if(root!= null && (root.freq>0)){   //其中某个节点词频 > 0  也需要把路径加入到paths

			paths.add(path+"|"+root.freq);
		}
		for (int i = root.MAX_SIZE-1; i >=0; i--) {
			if(root.digits[i]!=null){
				helper(root.digits[i],path+root.digits[i].val,paths);
			}
		}
	}
	
	//将词频字符串转换为长整数

	public String getLongInteger(ArrayList<String> arrs){
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < arrs.size(); i++) {
			String arr = arrs.get(i);
			String[] splits = arr.split("\\|");
			int count = Integer.parseInt(splits[1]);
			for (int j = 0; j < count; j++) {
				sb.append(splits[0]);
			}
		}
		
		return sb.toString();
	}
	
}