給一個二叉樹，每個節點都有權值，你可以從這個樹的節點往下走，到任意節點停止，你得到的分數是走過路徑上的權值的異或和，求可以獲得的最大分數，
輸入：第一行包含一個整數N,表示節點的數量，接下來N行每一行都有四個值，節點id，節點的權重，左節點id，右節點id，如果左右節點id=-1，表示沒有子節點，
輸出，可以獲得的最大分數，
例子：
5
1 1 2 3
2 4 -1 -1
3 2 -1 4
4 5 -1 5
5 3 -1 -1輸出：7
思路：這題和在二叉樹里面選取一段路徑，求路徑和等于給定值的所有路徑的題目差不多，相似之處在于，可以從任意節點出發，可以在任意節點結束，這種題目也是使用遞回，只不過需要兩個遞回函式，一個遞回函式process（root）用來計算以root為頭結點的子樹的所有結果，一個遞回函式count(root)計算，從root出發的所有可能結果，注意，以root為頭結點，不一定從root出發，
看代碼把：
public static class Node{
public Node left;
public Node right;
public int val;
public int id;
public Node(int val,int id){
this.val=val;
this.id=id;
this.left=null;
this.right=null;
}
}
public static HashMap<Integer,Node> map;//key為id，value為node
public static int res=0;//保存結果
public static void process(Node head,int xor){//表示以head為頭結點的
if(head==null)
return ;
count(head,xor);
process(head.left,xor);
process(head.right,xor);
}
public static void count(Node node,int xor){//從這個節點出發的異或
if(node==null) return ;
int tmp=xor^node.val;
res=Math.max(res, xor);
count(node.left,tmp);
count(node.right,tmp);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
map=new HashMap<>();
while(sc.hasNext()){
int N=sc.nextInt();
sc.nextLine();
int[][] info=new int[N][4];
for(int i=0;i<N;i++){
for(int j=0;j<4;j++){
info[i][j]=sc.nextInt();
}
Node node=new Node(info[i][1],info[i][0]);
map.put(info[i][0], node);
sc.nextLine();
}
Node head=null;
for(int i=0;i<info.length;i++){
int left=info[i][2];
int right=info[i][3];
int id=info[i][0];
Node node=map.get(id);
node.left=left==-1?null:map.get(left);
node.right=right==-1?null:map.get(right);
if(i==0){
head=node;
}
}
process(head,0);
System.out.println(res);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/6197.html
標籤：java
下一篇：01背包