一、相关概念

二、题目

题目

思路

利用二叉树的前序、中序遍历序列构建二叉树，并遍历构建好的二叉树。

• 利用递归的思路根据前序、中序序列构建二叉树
  
  相关下标

将二叉树节点结构定义成

class Node{
        int data;
        Node left;
        Node right;
        int sum;// 左子树、右子树之和
        public Node(int data){
            this.data=data;
        }
    }

• 构建好二叉树后进行后序遍历算出sum
  这个后序遍历（左右根）可以理解成：当前节点的左子树已经处理好、当前节点的右子树已经处理好，那么当前节点的

root.sum=root.left.data+root.left.sum+root.right.data+root.right.sum

代码

import java.util.Arrays;
import java.util.Scanner;

public class 树的遍历 {
    public static void main(String[] args) {
        new 树的遍历().exe();
    }

    class Node {
        // 节点数据域
        int data;
        Node left;
        Node right;
        int sum;// 左子树、右子树之和

        public Node(int data) {
            this.data = data;
        }
    }

    private void exe() {
        Scanner scan = new Scanner(System.in);
        String pre = scan.nextLine();
        String in = scan.nextLine();
        String[] preArr1 = pre.split(" ");
        String[] inArr1 = in.split(" ");
        // 前序遍历
        int[] preArr = new int[preArr1.length];
        for (int i = 0; i < preArr.length; i++) {
            preArr[i] = Integer.parseInt(preArr1[i]);
        }
        // 后序遍历
        int[] inArr = new int[inArr1.length];
        for (int i = 0; i < inArr.length; i++) {
            inArr[i] = Integer.parseInt(inArr1[i]);
        }
        System.out.println("pre:" + Arrays.toString(preArr));
        System.out.println("in:" + Arrays.toString(inArr));

        Node root = initTree(preArr, 0, preArr.length - 1, inArr, 0,
                inArr.length - 1);
        // 后序遍历
        postOrder(root);
        // 中序遍历
        inOrder(root);
    }

    // 树的中序遍历
    private void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        // 根
        System.out.print(root.sum + "\t");
        inOrder(root.right);
    }

    // 根据树的后序遍历构建求和树
    private void postOrder(Node root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        if (root.left != null && root.right != null) {
            root.sum = root.left.sum + root.left.data + root.right.data
                    + root.right.sum;
        } else if (root.left != null) {
            root.sum = root.left.sum + root.left.data;
        } else if (root.right != null) {
            root.sum = root.right.data + root.right.sum;
        } else {
            // nothing
        }
    }

    // 根据前序遍历、中序遍历构建二叉树
    private Node initTree(int[] preArr, int preStart, int preEnd, int[] inArr,
            int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        // 根节点
        int rootData = preArr[preStart];
        Node head = new Node(rootData);
        // 找到根节点在中序遍历序列中出现的位置
        int rootIndex = findInexInArray(inArr, inStart, inEnd, rootData);
        // 构建左子树
        // 左子树长度
        int leftLen = rootIndex - inStart;
        Node left = initTree(preArr, preStart + 1, preStart + leftLen, inArr,
                inStart, rootIndex - 1);
        // 构建右子树
        Node right = initTree(preArr, preStart + leftLen + 1, preEnd, inArr,
                rootIndex + 1, inEnd);
        head.left = left;
        head.right = right;
        return head;
    }

    // 寻找根节点在中序遍历中出现的位置 index
    private int findInexInArray(int[] inArr, int inStart, int inEnd,
            int rootData) {
        for (int i = inStart; i <= inEnd; i++) {
            if (inArr[i] == rootData) {
                return i;
            }
        }
        return -1;
    }

}

参考文献

程序员面试宝典