已知二叉树的前序和中序遍历序列，以此重建二叉树。
重建二叉树，必须知道前序和中序序列，其他组合都不行。
public class RebuildTree {
class Node{
int nodeValue;
Nodeleft;
Noderight;
Node(){}
Node(int nodeValue, Node left, Node right){
this.nodeValue = nodeValue;
this.left = left;
this.right = right;
}
Node(int nodeValue) {
this.nodeValue = nodeValue;
this.left =null;
this.right =null;
}
}
public NoderebuildTree(int[] preOrder, int[] inOrder)throws Exception {
if(preOrder ==null || preOrder.length ==0 || inOrder ==null || inOrder.length ==0){
throw new Exception("Invalid input!");
}
return constructTree(preOrder, 0, preOrder.length -1, inOrder, 0, inOrder.length -1);
}
private NodeconstructTree(int[] preOrder, int startIndex4PreOrder, int endIndex4PreOrder, int[] inOrder, int startIndex4InOrder, int endIndex4InOrder)throws Exception{
if(startIndex4PreOrder == endIndex4PreOrder){
if(startIndex4InOrder == endIndex4InOrder){
return new Node(preOrder[startIndex4PreOrder]);
}
throw new Exception("InValid input!");
}
//取preOrder的第一个数做root
int rootValue = preOrder[startIndex4PreOrder];
Node rootNode =new Node(rootValue);
//遍历inOrder找到rootValue
int rootIndex = findIndexOfNumber(inOrder, rootValue);
if(rootIndex == -1){
throw new Exception("InValid input!");
}
int leftTreeSize = rootIndex - startIndex4InOrder;
int rightTreeSize = endIndex4InOrder - rootIndex;
//如果leftTreeSize > 0，则存在左子树，创建左子树
if(leftTreeSize >0) {
rootNode.left = constructTree(preOrder, startIndex4PreOrder +1, startIndex4PreOrder + leftTreeSize, inOrder, startIndex4InOrder, startIndex4InOrder + leftTreeSize -1);
}
//如果rightTreeSize > 0，则存在右子树，创建右子树
if(rightTreeSize >0){
rootNode.right = constructTree(preOrder, startIndex4PreOrder + leftTreeSize +1, endIndex4PreOrder, inOrder, rootIndex +1, endIndex4InOrder);
}
return rootNode;
}
private int findIndexOfNumber(int[] seq, int num) {
for(int i =0; i < seq.length; i++) {
if(seq[i] == num){
return i;
}
}
return -1;
}
public ListpreOrderSeq(Node rootNode, List result){
//输出root节点
if(rootNode ==null){
return result;
}
result.add(rootNode.nodeValue);
//输出左子树
if(rootNode.left !=null) {
preOrderSeq(rootNode.left, result);
}
//输出右子树
if(rootNode.right !=null) {
preOrderSeq(rootNode.right, result);
}
return result;
}
public static void main(String[] args) {
try {
int[] preOrder = {10,6,3,8,15,13,17};
int[] inOrder = {3,6,8,10,13,15,17};
List result =new ArrayList<>();
RebuildTree rebuildTree =new RebuildTree();
result = rebuildTree.preOrderSeq(rebuildTree.rebuildTree(preOrder, inOrder), result);
for(Integer item : result){
System.out.println(" " + item +" ");
}
}catch (Exception e){}
}
}
网友评论