从二叉查找树到链接列表数组

Question

通过从左到右遍历数组并插入每个元素，创建了一个二叉搜索树。这棵树可能不是一棵平衡的树。给定一个具有不同元素的二元搜索树，打印所有可能导致该树的数组。

为了回答这个问题，我编写了以下代码。尽管如此，它似乎并没有打印出所有可能导致所有情况下的树的所有可能数组。你认为应该修改什么？

public class Main {

  public static LinkedList<Integer> passed = new LinkedList<>();
    public static LinkedList<BinaryTree> notyet = new LinkedList<>();
    public static ArrayList<LinkedList<Integer>> results = new ArrayList<LinkedList<Integer>>();



public static void main(String args[]) {
    BinaryTree tr = readTree();
    ArrayList<LinkedList<Integer>> result = allSequences(tr);
    for (LinkedList<Integer> l : result){
        for(int elem: l) System.out.print(elem+" ");
        System.out.println("");
    }
}
private static BinaryTree readTree() {
    BinaryTree tr = new BinaryTree(2, null, null);
    tr.left = new  BinaryTree(1, null, null);
    tr.right = new  BinaryTree(3, null, null);
    return tr;
}

public static ArrayList<LinkedList<Integer>> allSequences(BinaryTree tr){
    // implement here
    ArrayList<LinkedList<Integer>> result = new ArrayList<LinkedList<Integer>>();


    findseqs(passed,notyet,tr);
    //result=results.clone();
    for(LinkedList<Integer> sample :results){
        result.add(sample);
    }


    return result;
}


public static void findseqs(LinkedList<Integer> passed, LinkedList<BinaryTree> notyet, BinaryTree tr) {
    passed.add(tr.value);

    if (tr.left != null) notyet.add(tr.left);
  if (tr.right != null) notyet.add(tr.right);

  if (notyet.isEmpty()) {
    results.add(passed);
  }

  for (BinaryTree elem: notyet) {
    LinkedList<Integer> temp = (LinkedList<Integer>) passed.clone();
    LinkedList<BinaryTree> ptemp = (LinkedList<BinaryTree>) notyet.clone();
    ptemp.remove(elem);
    findseqs(temp, ptemp, elem);
  }


  }

Answer 1

关于数组的意义在于，如果A是图中B的祖先，那么A在数组中先于B。除此之外，没有什么是可以假定的。因此，可以通过以下递归函数生成数组。

function sourceArrays(Tree t)

  // leafe node
  if t == null
    return empty list;

  r = root(t);
  append r to existing arrays;

  la = sourceArrays(t.left);
  ra = sourceArrays(t.right);

  ac = createArrayCombitations(la, ra);
  append ac to existing arrays;

end

function createArrayCombitations(la, ra)


  foreach a in la
    foreach b in ra
      r = combineArrays(a,b);
      add r to result;
    end
  end

end

function combineArrays(a, b)
  generate all combinations of elements from two array such that order of elements in each array is preserved.
  Ie if x precedes y in a or b the x precedes y in result