만 이 진 트 리 를 구 화 트 리 로 변환 합 니 다.

17359 단어
      ,            

      :       ,            ,                         。

   :
                  10
               /      \
             -2        6
           /   \      /  \ 
          8    -4    7    5

   :
                 20(4-2+12+6)
               /      \
           4(8-4)      12(7+5)
            /   \      /  \ 
          0      0    0    0

            ,         ;
          int;


    :
2   , 1           , 2           ,     

    :
1   ,          ,     

    1:
10 -2 8 -4 6 7 5
8 -2 -4 10 7 6 5

    1:
0 4 0 20 0 12 0

import java.util.Scanner;

public class Main {
	
	public static class TreeNode{
		int value;
		TreeNode left;
		TreeNode right;
		int old_value;
 		TreeNode(int value, TreeNode left, TreeNode right){
			this.value = value;
			this.left = left;
			this.right = right;
		}
	}
	
	public static TreeNode construct(int[] pre, int p_start, int p_end, int[] in, int i_start, int i_end) {
		if(p_end<p_start || i_start>i_end) {
			return null;
		}
		int index = -1;
		TreeNode root = new TreeNode(pre[p_start], null, null);
		for(int i=i_start; i<=i_end; i++) {
			if(in[i]==pre[p_start])
				index = i;
		}
		root.left = construct(pre, p_start+1, p_start+index-i_start, in, i_start, index-1);
		root.right = construct(pre, p_start+index-i_start+1, p_end, in, index+1, i_end);
		return root;
		
	}
	
	public static void back_order(TreeNode root) {
		if(root==null)
			return;
		if(root.left==null && root.right==null)
				{root.old_value = root.value; root.value=0; return;}
		back_order(root.left);
		back_order(root.right);
		int old_left_value = (root.left!=null)? root.left.old_value:0;
		int old_right_value = (root.right!=null)? root.right.old_value: 0;
		root.old_value = root.value + old_left_value + old_right_value;
		root.value = old_left_value + old_right_value;
		
	}
	
	public static void in_print(TreeNode root) {
		if(root==null)
			return;
		in_print(root.left);
		System.out.print(root.value);
		System.out.print(" ");
		in_print(root.right);
	}
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		String pre_str = scan.nextLine();
		String[] p = pre_str.split(" ");
		int [] pre = new int[p.length];
		int i = 0;
		for(String s: p) {
			pre[i++] = Integer.parseInt(s);
		}
		String in_str = scan.nextLine();
		String [] in = in_str.split(" ");
		i = 0;
		int [] in_list = new int[in.length];
		for(String s: in) {
			in_list[i++] = Integer.parseInt(s);
		}
		
		TreeNode root = construct(pre, 0, pre.length-1, in_list, 0, in_list.length-1);
		back_order(root);
		in_print(root);
	}
}

좋은 웹페이지 즐겨찾기