一、相关概念
二、题目
题目
思路
利用二叉树的前序、中序遍历序列构建二叉树，并遍历构建好的二叉树。
-
利用递归的思路根据前序、中序序列构建二叉树
相关下标
将二叉树节点结构定义成
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;
}
}
