題目描述

image.png

image.png

題目分析

1. 利用前序遍歷和中序遍歷創(chuàng)建樹
2. 通過(guò)遞歸獲取子節(jié)點(diǎn)的和，最后求得根節(jié)點(diǎn)的和
3. 最后利用遞歸得到中序遍歷的結(jié)果

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Tree{
    TreeNode root;
    public Tree(){
        root = null;
    }
    public TreeNode create(int b1,int b2, int m1,int m2,int[]before,int[]mid){
        if(b2 < b1 || m2 < m1)
            return null;
        TreeNode node = new TreeNode(before[b1]);
        int index = 0;
        for(int i = m1;i <= m2;i++){
            if(mid[i] == before[b1]){
                index = i;//找到下標(biāo)
            }
        }
        node.left = create(b1+1,b1+(index-m1),m1,index-1,before,mid);
        node.rigth = create(b1+(index-m1+1),b2,index+1,m2,before,mid);

        return node;
    }
    public void createTree(int[] before,int[] mid){
    //創(chuàng)建樹
        root = create(0,before.length-1,0,mid.length-1,before,mid);
    }


    public int getChild(TreeNode node){
        if(node == null)
            return 0;
        if(node.left == null && node.rigth == null){
            int temp = node.data;
            node.data = 0;
            return temp;
        }
        else {
            int temp = node.data;
            node.data = getChild(node.left)+getChild(node.rigth);
            return node.data + temp;
        }
    }
    
    public void trans(){
        TreeNode node = root;
        node.data = getChild(node.left)+getChild(node.rigth);

    }

    public void printMid(TreeNode node,List<Integer> list){
        if(node == null)
            return;
        printMid(node.left,list);
        list.add(node.data);
        printMid(node.rigth,list);
    }
    public List<Integer> print(int type){
        List<Integer> list = new ArrayList<>();
        switch (type){
            case 1:
                printMid(root,list);
        }
        return list;
    }
}
class TreeNode{
    TreeNode left;
    TreeNode rigth;
    int data;
    public TreeNode(int i){
        this.data = i;
    }
}
public class Main{
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[]A = br.readLine().split(" ");
        String[]B = br.readLine().split(" ");
        int len = A.length;
        int before[] = new int[len];
        int mid[] = new int[len];
        for(int i = 0; i < len;i++){
            before[i] = Integer.valueOf(A[i]);
        }
        for(int i = 0; i < len;i++){
            mid[i] = Integer.valueOf(B[i]);
        }

        Tree tree = new Tree();
        tree.createTree(before,mid);
        tree.trans();
        List<Integer> list = tree.print(1);
        for(Integer i : list){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}