【无标题】
算法题目描述：
输入2行整数，第1行表示二叉树的中序遍历，第2行表示二叉树的前序遍历，以空格分割。
请由该二叉树生成一个新的二叉树，它满足其树中的每个节点将包含原始树中的左子树和右子树的和。
开始之前说一下二叉树的遍历特点：
前序遍历输出的顺序是父节点，左节点，右节点。
中序遍历输出的顺序是左节点，右节点，父节点。
后序遍历输出的顺序是右节点，左节点，父节点。
当然顺序还跟你先输出左右也有关系。
首先是遍历的例子：
public static void main(String[] args) {
Tree root = new Tree(6);
Tree t7 = new Tree(7);
root.left = t7;
Tree t9 = new Tree(9);
root.right = t9;
Tree t_2 = new Tree(-2);
t7.right = t_2;
Tree t6 = new Tree(6);
t9.left = t6;
Tree t5 = new Tree(5);
t7.left = t5;
Tree t3 = new Tree(3);
t9.right = t3;
// Tree t6_ = new Tree(6);
// t5.left = t6_;
//
// t5.right = t3;
prePrint(root);
System.out.println();
inPrint(root);
System.out.println();
afterPrint(root);
}
public static void prePrint(Tree root) {
if (root == null) {
return;
}
System.out.print(root.value + " ");
prePrint(root.left);
prePrint(root.right);
}
public static void inPrint(Tree root) {
if (root == null) {
return;
}
inPrint(root.left);
System.out.print(root.value + " ");
inPrint(root.right);
}
public static void afterPrint(Tree root) {
if (root == null) {
return;
}
afterPrint(root.left);
afterPrint(root.right);
System.out.print(root.value + " ");
}
static class Tree {
int value;
Tree left;
Tree right;
public Tree() {
}
public Tree(int value) {
this.value = value;
}
}
然后是该题目的代码：
根据三个遍历中的两个可以确定一颗二叉树。比如前序和中序数组：
思路：1，中序数组的第一个元素肯定是root元素
2，根据root元素在前序数组中分出左右子树。
3，在左右子树的中序数组找出root元素，其中左子树的root元素是第一步root的左节点，右子树的root元素是右节点一次递归。
4，注意元素的值是左右子树的和。
public static void main(String[] args) {
// int[] inArr = new int[]{6,5,3 ,7, -2, 6, 6, 9, 3};
// int[] preArr = new int[]{6 ,7, 5, 6, 3, -2, 9, 6, 3};
// int[] inArr = new int[]{6,5};
// int[] preArr = new int[]{6 ,5};
int[] preArr = new int[]{10, -2, 8, -4, 6, 7, 5};
int[] inArr = new int[]{8, -2, -4, 10, 7, 6, 5};
final Tree tree = buildTree(inArr, preArr);
inPrint(tree);
System.out.println();
prePrint(tree);
}
public static Tree buildTree(int[] inArr, int[] preArr) {
//校验数据
if (inArr.length == 0 || inArr.length != preArr.length) {
return null;
}
//前序遍历的第一个元素就是 root
Tree root = new Tree();
if (inArr.length == 1) {
root.value = 0;
return root;
//递归的逻辑就是先找到root
// 然后root.left=左子树的root
// root.right=右子树的root
//问题变成寻找左右子树
// 然后递归。
}
//如果只有两个值判断是左元素还是右元素
if (inArr.length == 2) {
Tree tree = new Tree(0);
for (int i = 0; i < 2; i++) {
if (inArr[0] == preArr[0]) {
root.right = tree;
root.value = preArr[1];
} else {
root.left = tree;
root.value = preArr[0];
}
}
return root;
}
//在中序遍历中找到root元素，左边的就是左子树，右边的就是右子树
for (int i = 1; i < inArr.length; i++) {
if (inArr[i] == preArr[0]) {
//可能是根节点
int[] inLeftArr = Arrays.copyOfRange(inArr, 0, i);
int[] preLeftArr = Arrays.copyOfRange(preArr, 1, i + 1);
int[] inRightArr = Arrays.copyOfRange(inArr, i + 1, inArr.length);
int[] preRightArr = Arrays.copyOfRange(preArr, i + 1, preArr.length);
root.value = sum(inLeftArr) + sum(inRightArr);
//判断左右子树是否相等
if (arrEquals(inLeftArr, preLeftArr) && arrEquals(inRightArr, preRightArr)) {
root.left = buildTree(inLeftArr, preLeftArr);
root.right = buildTree(inRightArr, preRightArr);
break;
}
}
}
return root;
}
public static int sum(int[] arr) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
public static boolean arrEquals(int[] a1, int[] a2) {
int[] arr1 = Arrays.copyOf(a1, a1.length);
int[] arr2 = Arrays.copyOf(a2, a2.length);
Arrays.sort(arr1);
Arrays.sort(arr2);
return Arrays.equals(arr1, arr2);
}
public static void prePrint(Tree root) {
if (root == null) {
return;
}
System.out.print(root.value + " ");
prePrint(root.left);
prePrint(root.right);
}
public static void inPrint(Tree root) {
if (root == null) {
return;
}
inPrint(root.left);
System.out.print(root.value + " ");
inPrint(root.right);
}
public static void afterPrint(Tree root) {
if (root == null) {
return;
}
afterPrint(root.left);
afterPrint(root.right);
System.out.print(root.value + " ");
}
static class Tree {
int value;
Tree left;
Tree right;
public Tree() {
}
public Tree(int value) {
this.value = value;
}
}
原文地址：https://blog.csdn.net/lx18854869896/article/details/140560937
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！