8/5 DS 二元樹
===
###### tags: `Coding X` `DS`
[TOC]

## Lab Challenage

### Lab 5 build a Binary Tree

package tree;

import java.util.ArrayList;
import java.util.Scanner;
import java.lang.Math;

public class Tree {
	public static int log2(int x)
	{
	    return (int)(Math.log(x) / Math.log(2));
	}
	public static int pow(int x, int y) {
		int res =1;
		for(int i= 0; i<y; i++) {
			res *=x;
		}
		return res;
	}
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int pathsum = input.nextInt();
		ArrayList <Integer> Tree_arrlist = new ArrayList<Integer>(); 
		while(true) {
			int usr_input = input.nextInt();
			if(usr_input == 0) {
				break;
			}else if(usr_input == -1){
				Tree_arrlist.add(null);
			}else {
				Tree_arrlist.add(usr_input);
			}
		}
		int size =Tree_arrlist.size();
		boolean find = false;
		int nodeIndex = size -1;
		int sum, tmp; 
		int layer = log2(size); // 求樹有幾層
		int leaf = pow(2,layer); // 求葉子數量	
		while(leaf>0) {
			tmp = nodeIndex;
			sum = 0; // 重置sum
			while(tmp >=0) {
				if(Tree_arrlist.get(tmp)!=null) {
					sum += Tree_arrlist.get(tmp);
				}
				if(tmp%2 ==0) {
					tmp = tmp/2-1;
				}else {
					tmp =tmp/2;
				}
				
			}
			if(sum==pathsum) {
				find = true;
				System.out.println("True");
				break;
			}
			// 更新 nodeIndex and leaf
			nodeIndex--; 
			leaf--;
		}
		if(find==false) {
			System.out.println("False");
		}
		
		}
	
	}