Giải pháp Java:
import java.util.HashMap;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;
public class InorderLevelorder {
private static int[] levelArray;
public static void main(String[] args) {
//in order traversal of binary tree
int[] in = {4,10,3,1,7,11,8,2};
//level order traversal of binary tree
int[] lev = {7,10,2,4,3,8,1,11};
//Builds a Binary Tree and returns the root node
buildTree(in, lev);
}
private static BinaryTreeNode buildTree(int[] in, int[] lev){
//Hash the values of both the arrays for O(1) time search
HashMap<Integer, Integer> inMap = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> levMap = new HashMap<Integer, Integer>();
levelArray = lev;
for(int i=0;i<in.length;i++)
inMap.put(in[i], i);
for(int j=0;j<lev.length;j++)
levMap.put(lev[j], j);
return buildTree(in, lev, 0, in.length - 1, inMap, levMap);
}
//recursive method that constructs the binary tree
private static BinaryTreeNode buildTree(int[] in, int[] lev, int inStart, int inEnd, HashMap<Integer, Integer> inMap, HashMap<Integer, Integer> levMap){
if(inStart > inEnd)
return null;
int nodeVal = lev[0];
BinaryTreeNode node = new BinaryTreeNode();
node.setData(nodeVal);
if(inStart == inEnd)
return node;
int inIndex = inMap.get(nodeVal);
int[] leftSubTree = subArray(in, levelArray, inStart, inIndex-1, inMap, levMap);
int[] rightSubTree = subArray(in, levelArray, inIndex+1, inEnd, inMap, levMap);
node.setLeftNode(buildTree(in, leftSubTree, inStart, inIndex-1, inMap, levMap));
node.setRightNode(buildTree(in, rightSubTree, inIndex+1, inEnd, inMap, levMap));
return node;
}
private static int[] subArray(int[] in, int[] lev, int inStart, int inEnd, HashMap<Integer, Integer> inMap, HashMap<Integer, Integer> levMap){
int[] newSubArray = new int[inEnd - inStart + 1];
SortedSet<Integer> set = new TreeSet<Integer>();
for(int i=inStart;i<=inEnd;i++){
int levIndex = levMap.get(in[i]);
set.add(levIndex);
}
int j=0;
Iterator<Integer> iter = set.iterator();
while(iter.hasNext()){
int levIndex = iter.next();
int levValue = lev[levIndex];
newSubArray[j] = levValue;
j++;
}
return newSubArray;
}
}
class BinaryTreeNode {
private int data;
private BinaryTreeNode leftNode;
private BinaryTreeNode rightNode;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BinaryTreeNode getLeftNode() {
return leftNode;
}
public void setLeftNode(BinaryTreeNode leftNode) {
this.leftNode = leftNode;
}
public BinaryTreeNode getRightNode() {
return rightNode;
}
public void setRightNode(BinaryTreeNode rightNode) {
this.rightNode = rightNode;
}
}
Huh ... chỉ tò mò, là bài tập về nhà này? :) – Mehrdad
Xin lỗi, đã phải đề cập đến nó trước đây. Không, nó không phải là một bài tập về nhà. Tôi đang cố gắng giải quyết http://stackoverflow.com/questions/4539698/finding-a-preorder-of-some-digits-with-their-levels-in-bst này và tôi chắc chắn, nó có thể được giải quyết nếu chúng tôi có bằng chứng cho việc này. –