快手9.25笔试第二题,自己的测试用例过了
import java.util.*; public class kuaishou02 { static class node{ int v=0; int s=0; node l=null; node r=null; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); String[] sarr=sc.nextLine().split(" "); int[] qarr=new int[sarr.length]; for(int i=0;i<sarr.length;i++) { qarr[i]=Integer.parseInt(sarr[i]); } sarr=sc.nextLine().split(" "); int[] zarr=new int[sarr.length]; for(int i=0;i<sarr.length;i++) { zarr[i]=Integer.parseInt(sarr[i]); } node head=constructTree(qarr,0,qarr.length-1,zarr,0,zarr.length-1); hvisit(head); ArrayList<Integer> list=new ArrayList<Integer>(); zvisit(head,list); for(int i=0;i<list.size();i++) { if(i==list.size()-1) { System.out.print(list.get(i)); }else { System.out.print(list.get(i)+" "); } } System.out.println(); } public static void zvisit(node head,ArrayList<Integer> list) { if(head==null) { return; }else { zvisit(head.l,list); if(head.l==null&&head.r==null) { list.add(0); }else { list.add(head.s); } zvisit(head.r,list); } }; public static void hvisit(node head){ if(head==null) { return; }else if(head.l==null&&head.r==null){ head.s=head.v; }else if(head.l==null&&head.r!=null){ hvisit(head.r); head.s=head.v+head.r.s; }else if(head.l!=null&&head.r==null){ hvisit(head.l); head.s=head.v+head.l.s; }else{ hvisit(head.l); hvisit(head.r); head.s=head.v+head.l.s+head.r.s; } } public static node constructTree(int[] qarr,int qs,int qe,int[] zarr,int zs,int ze) { if(qs>qe) { return null; }else { node head=new node(); head.v=qarr[qs]; int i=zs; while(zarr[i]!=qarr[qs]) { i++; }; i--; head.l=constructTree(qarr,qs+1,qs+i-zs+1,zarr,zs,i); head.r=constructTree(qarr,qs+i-zs+2,qe,zarr,i+2,ze); return head; } } }
#Java工程师##笔试题目##测试##快手#