求和树--前序、中序序列递归构建二叉树

import java.util.*;

public class SumTree {

static int[] preOrder;
static int[] inOrder;
static List<Integer> inOrderRes;

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String[] str1 = sc.nextLine().trim().split(" ");
    String[] str2 = sc.nextLine().trim().split(" ");
    int len = str1.length;

    preOrder = new int[len];
    inOrder = new int[len];

    for (int i = 0; i < len; i++) {
        preOrder[i] = Integer.parseInt(str1[i]);
        inOrder[i] = Integer.parseInt(str2[i]);
    }

    // 存放求和后的中序序列
    inOrderRes = new ArrayList<>();
    // 构建树，返回root节点
    Node root = buildTree(0, 0, len - 1);// len - 1 =
                                            // 6，结尾处索引必须是<=(67行)子序列末端，不能是len = 7（这样右子树会出问题），
    sumNode(root);
    inOrderTral(root);
    for (int i : inOrderRes) {
        System.out.print(i + " ");
    }
    System.out.println();
}

// 中序遍历
static void inOrderTral(Node node) {
    if (node == null)
        return;
    inOrderTral(node.left);
    inOrderRes.add(node.sum);
    inOrderTral(node.right);
}

// 根据构建的二叉树补充sum值
static void sumNode(Node node) {
    if (node.left == null && node.right == null) {
        node.sum = 0;
    } else if (node.left == null) {
        sumNode(node.right);
        node.sum = node.right.sum + node.right.val;
    } else if (node.right == null) {
        sumNode(node.left);
        node.sum = node.left.sum + node.left.val;
    } else {
        sumNode(node.left);
        sumNode(node.right);
        node.sum = node.left.sum + node.left.val + node.right.sum
                + node.right.val;
    }
}

// 递归构建二叉树
static Node buildTree(int root, int start, int end) {
    if (start > end)    // 当start == end时，就是叶子节点了
        return null;
    // 创建一个root节点
    Node node = new Node(preOrder[root]);
    int index = 0;// 记录root在中序序列中的下标
    int count = 0;// 记录在前序中root右孩子与root的距离
    for (int i = start; i <= end; i++) {
        count++;
        if (preOrder[root] == inOrder[i]) {
            index = i;
            break;
        }
    }
    // 递归构建当前节点的左右子树
    node.left = buildTree(root + 1, start, index - 1);// 前序中root右边第一个位置即左孩子
    // 注意右孩子在前序序列中的下标root + count
    node.right = buildTree(root + count, index + 1, end);
    return node;
}

}

public class Node {

Node left = null;
Node right = null;
int val;
int sum;
public Node(int value) {
    val = value;
}

}