假设是1000个结点以内，
输入前序 4 1 3 2 6 5 7
中序 1 2 3 4 5 6 7
得到后续 2 3 1 5 7 6 4
已知前序遍历中序遍历求后序遍历：
代码语言：javascript复制import java.io.BufferedInputStream;
import java.util.Scanner;
class Node {
int data;
Node left, right;
}
public class Main {
public static int[] pre = new int[1001];
public static int[] in = new int[1001];
public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int n = cin.nextInt();
for (int i = 0; i < n; i) {
pre[i] = cin.nextInt();
}
for (int i = 0; i < n; i) {
in[i] = cin.nextInt();
}
cin.close();
Node head = createTree(pre, 0, in, 0, n);
postTraverse(head);
}
public static void postTraverse(Node node) {
if (node == null)
return;
postTraverse(node.left);
postTraverse(node.right);
System.out.print(node.data " ");
}
// 已知先序中序，建树
// @param pre 先序遍历的数组
// @param lo 先序遍历的起点下标
// @param in 中序遍历的数组
// @param ini 中序遍历的起点下标
// @param n 这个树的结点个数
public static Node createTree(int[] pre, int lo, int[] in, int ini, int n) {
if (n <= 0) {
return null;
}
Node node = new Node();
node.data = pre[lo];
int i;
for (i = 0; i < n; i) {
if (pre[lo] == in[ini i]) // 寻找到该树的根节点就又可以划分左右子树查找了
break;
}
node.left = createTree(pre, lo 1, in, ini, i); // 左区间
node.right = createTree(pre, lo i 1, in, ini i 1, n - i - 1); // 右区间
// 最后一个参数是这个子树的有多少结点
return node;
}
}题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
练习题地址：
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
AC代码：
代码语言：javascript复制/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
return reConstructBinaryTree1(pre, 0, in, 0, in.length);
}
private TreeNode reConstructBinaryTree1(int[] pre, int lo, int[] in, int ini, int n) {
if (n <= 0)
return null;
TreeNode node = new TreeNode(pre[lo]);
int i;
for (i = 0; i < n; i) {
if (pre[lo] == in[ini i])
break;
}
node.left = reConstructBinaryTree1(pre, lo 1, in, ini, i);
node.right = reConstructBinaryTree1(pre, lo i 1, in, ini i 1, n - i - 1);
return node;
}
}
