問題: プレオーダー配列が与えられた場合、それを二分探索木に変換します
7
5 9
3 6 8 10
解決:
ステップ 1: 配列を Stack に変換する
スタックからポップされた最初の要素はルートです。
次の要素と比較し、ルート値より小さい場合は左サブツリーにし、そうでない場合は右サブツリーにします
ここにコードがあります
public class reconstruct{
public static void main(String[] args){
Stack s = new Stack();
Integer[] arr = {7,5,3,6,9,8,10};
List<Integer> l = Arrays.asList(arr);
for (int i=arr.length-1; i>=0;i--){
s.push(arr[i]);
}
System.out.println(s);
Node newone = CreateFromPreOrder(s);
printInorder(newone);
public static Node CreateFromPreOrder(Stack preOrder) {
if (!preOrder.isEmpty()) {
//System.out.println("hel");
int value = (int) preOrder.pop();
Node root = new Node(value);
if (!preOrder.isEmpty()){
if((int)preOrder.peek()<value){
root.left=CreateFromPreOrder(preOrder);
}
else
root.right = CreateFromPreOrder(preOrder);
}
return root;
}
else return null;
}
public static void printInorder(Node root) {
if (root!=null){
printInorder(root.left);
System.out.print(" " + root.data);
printInorder(root.right);
}
}
}
Output:
[10, 8, 9, 6, 3, 5, 7]
3 6 8 10 9 5 7
出力は、予期される順序配列ではありません。上記のロジックの何が問題なのかわかりません。