package cs;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
/**
*
5
5:4|7
4:3|8
7:2|-1
3:-1|-1
8:-1|-1
2:-1|-1
* [@author](/user/author)
*
*/
public class quna {
static int isT=1;
static List<Integer> tem=new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
List<Integer> list=new ArrayList<>();
Set<Integer> set= new HashSet<>();
int n=in.nextInt();
list.add(n);
set.add(n);
while(set.size()!=0){
String s=in.next();
String[] root = s.split(":");
int rt=Integer.parseInt(root[0]);
if(set.contains(rt)){
set.remove(rt);
}
else{
set.add(rt);
}
int lch=Integer.parseInt(root[1].substring(0, root[1].indexOf("|")));
int rch=Integer.parseInt(root[1].substring(root[1].indexOf("|")+1,root[1].length()));
if(lch!=-1){
list.add(lch);
set.add(lch);
}
if(rch!=-1){
list.add(rch);
set.add(rch);
}
}
//List<Integer> tem=new ArrayList<>();
//tem.add(list.get(0));
zhong(list,0);
for(int i=0;i<tem.size()-1;i++){
//System.out.println(tem.get(i));
if(tem.get(i)>tem.get(i+1)){
System.out.println(0);
return;
}
}
System.out.println(1);
}
public static void zhong(List<Integer> list,int i){
int l=(i+1)*2-1;
int r=(i+1)*2;
if(i>=list.size()){
return;
}
if(i>=list.size()){
return;
}
if(l<list.size()){
zhong(list,l);
}
tem.add(list.get(i));
if(r<list.size()){
zhong(list,r);
}
}
}
我跟你一样啊,不知道如何解决输入的问题 ,已经写出来了 ,就是不知道输入怎么解决 。。。。。。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; /* * 5 5:4|7 4:3|8 7:2|-1 3:-1|-1 8:-1|-1 2:-1|-1 * */ public class Main_2 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); HashMap<Integer, Integer[]> map = new HashMap<>(); String s = br.readLine(); Integer rootval = Integer.parseInt(s.charAt(0) + ""); String str = null; while((str = br.readLine()) != null){ Integer temp1 = Integer.parseInt(str.charAt(0) + ""); Integer[] temp2 = new Integer[2]; int startIndex = str.indexOf(":")+1; int endIndex = str.indexOf("|"); String s1 = str.substring(startIndex, endIndex); String s2 = str.substring(endIndex+1); temp2[0] = Integer.parseInt(s1); System.out.println(temp2[0]); temp2[1] = Integer.parseInt(s2); System.out.println(temp2[1]); map.put(temp1, temp2); } TreeNode root = creatTree(rootval, map); ArrayList<Integer> arr = new ArrayList<>(); inOrderTraversal(root, arr); boolean flag = isOrdered(arr); if(flag) System.out.println(1); else System.out.println(0); } public static TreeNode creatTree(Integer rootVal, HashMap<Integer, Integer[]> map){ LinkedList<TreeNode> queue = new LinkedList<>(); // 队列 TreeNode root = new TreeNode(rootVal); //构造根节点 queue.add(root); while(!queue.isEmpty()){ TreeNode node = queue.poll(); Integer[] values = map.get(node); if(values[0] != -1){ //有左儿子 TreeNode leftChild = new TreeNode(values[0]); node.left = leftChild; queue.add(leftChild); } if(values[1] != -1){ //有右儿子 TreeNode rightChild = new TreeNode(values[1]); node.right = rightChild; queue.add(rightChild); } } return root; } public static void inOrderTraversal(TreeNode root, ArrayList<Integer> arr){ if(root == null) return; inOrderTraversal(root.left, arr); arr.add(root.val); inOrderTraversal(root.right, arr); } public static boolean isOrdered(ArrayList<Integer> arr){ int temp = arr.get(0); for (int i = 1; i < arr.size(); i++) { if(temp < arr.get(i)) temp = arr.get(i); else return false; } return true; } } class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode(int val){ this.val = val; } }
先用leftmap, rightmap分别存储左右儿子值; private static Map<Integer, Integer> leftmap = new HashMap<Integer, Integer>(); private static Map<Integer, Integer> leftmap = new HashMap<Integer, Integer>(); 树结构 public static class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val;} } 建立根节点 root = new TreeNode(val); 获得树 getTree(root); public void getTree(TreeNode root){ if (leftmap.containsKey(root.val)){ if (leftmap.get(root.val) != -1){ root.left = new TreeNode(leftmap.get(root.val)); getTree(root.left); } if (rightmap.get(root.val) != -1){ root.right = new TreeNode(rightmap.get(root.val)); getTree(root.right); } } }