树的遍历(已知前序遍历中序遍历求后序遍历，或者已知后序中序求先序)

importjava.io.BufferedInputStream;
importjava.util.Scanner;
classNode {
intdata;
Nodeleft, right;
}
publicclassMain {
publicstaticint[] pre=newint[1001];
publicstaticint[] in=newint[1001];
publicstaticvoidmain(String[] args) {
Scannercin=newScanner(newBufferedInputStream(System.in));
intn=cin.nextInt();
for (inti=0; i<n; ++i) {
pre[i] =cin.nextInt();
        }
for (inti=0; i<n; ++i) {
in[i] =cin.nextInt();
        }
cin.close();
Nodehead=createTree(pre, 0, in, 0, n);
postTraverse(head);
    }
publicstaticvoidpostTraverse(Nodenode) {
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 这个树的结点个数publicstaticNodecreateTree(int[] pre, intlo, int[] in, intini, intn) {
if (n<=0) {
returnnull;
        }
Nodenode=newNode();
node.data=pre[lo];
inti;
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); // 右区间// 最后一个参数是这个子树的有多少结点returnnode;
    }
}

/*** Definition for binary tree* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/publicclassSolution {
publicTreeNodereConstructBinaryTree(int[] pre, int[] in) {
returnreConstructBinaryTree1(pre, 0, in, 0, in.length);
    }
privateTreeNodereConstructBinaryTree1(int[] pre, intlo, int[] in, intini, intn) {
if (n<=0)
returnnull;
TreeNodenode=newTreeNode(pre[lo]);
inti;
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);
returnnode;
    }
}