轉換樹的序陣列（遞歸）

Question

我想樹轉換成例如其序排列，如果樹是這樣的：

                           /        \
                                                                                                ________
然後其預訂陣列應採用  | 1 | 2 | 3 |
                                                                                                              - - - - - - - -

這裏有一些樹輸入：

// 2 3 4 5 6 7 8 -1 -1 -1 -1 -1 -1 -1 -1 
// 10 9 4 -1 -1 5 8 -1 6 -1 -1 3 -1 -1 -1 
// 1 2 9 3 4 -1 10 5 -1 -1 5 -1 -1 -1 -1 -1 6 -1 7 -1 8 -1 -1 
// 1 2 6 3 7 -1 -1 4 -1 -1 8 5 -1 -1 9 -1 -1 -1 10 -1 -1 
// 1 2 3 -1 -1 -1 -1 

代碼在我主要。Java的：

public class Main { 
    public static void main(String[] args) throws QueueEmptyException { 
     Scanner in = new Scanner(System.in); 

     BinaryTreeNode<Integer> root = BinaryTreeNode.takeInput_LEVEL_WISE(in);  // tree input taken 
     BinaryTreeNode.print_Binary_Tree_LEVEL_WISE(root); 

     // create its preOrder array 
     int pre[] = BinaryTreeNode.preOrder_Array(root); 
     for (int val : pre) { 
      System.out.print(val + " "); 
     } 

     // create its postOrder array 
    } 
} 

這裏是我的樹節點：

public class BinaryTreeNode<T> { 
    public T data; 
    public BinaryTreeNode<T> left; 
    public BinaryTreeNode<T> right; 

    BinaryTreeNode(T data) { 
     this.data = data; 
     left = null; 
     right = null; 
    } 
} 

的取輸入法：（在此沒有問題）

public static BinaryTreeNode<Integer> takeInput_LEVEL_WISE(Scanner in) { 
     Queue<BinaryTreeNode<Integer>> q = new LinkedList<>(); 
     System.out.println("enter root "); 
     int data = in.nextInt(); 
     if (data == -1)    // no root is formed 
      return null; 
     BinaryTreeNode<Integer> root = new BinaryTreeNode<>(data); 
     q.add(root); 

     int left, right; 
     while (!q.isEmpty()) { 
      BinaryTreeNode<Integer> currentRoot = q.poll(); 
      System.out.println("enter left of " + currentRoot.data + " : "); 
      left = in.nextInt(); 

      if (left == -1) { 
       currentRoot.left = null; 
      } else { 
       BinaryTreeNode<Integer> leftChild = new BinaryTreeNode<>(left); 
       currentRoot.left = leftChild; 
       q.add(leftChild); 
      } 


      System.out.println("enter right of " + currentRoot.data + " : "); 
      right = in.nextInt(); 
      if (right == -1) { 
       currentRoot.right = null; 
      } else { 
       BinaryTreeNode<Integer> rightChild = new BinaryTreeNode<>(right); 
       currentRoot.right = rightChild; 
       q.add(rightChild); 
      } 
     } 
     return root; 
    } 

代碼打印功能：（在這個也沒問題）

public static void print_Binary_Tree_LEVEL_WISE(BinaryTreeNode<Integer> root) { 
     Queue<BinaryTreeNode<Integer>> q = new LinkedList<>(); 
     q.add(root); 

     String print = ""; 
     while (q.size() != 0) {  // until not empty 
      BinaryTreeNode<Integer> currentRoot = q.poll(); 
      print = currentRoot.data + ":"; 

      // adding the right and left 
      if (currentRoot.left != null) { 
       q.add(currentRoot.left); 
       print += "L:" + currentRoot.left.data + ","; 
      } else { 
       print += "L:" + -1 + ","; 
      } 
      if (currentRoot.right != null) { 
       q.add(currentRoot.right); 
       print += "R:" + currentRoot.right.data; 
      } else { 
       print += "R:" + -1; 
      } 

      System.out.println(print); 
     } 
    } 

---

這裏是預購數組的代碼：（此面臨的問題）

public static int[] preOrder_Array(BinaryTreeNode<Integer> root) { 
     if (root == null) 
      return new int[0];  // array of 0 size 

     int n = noOfNodesIN_Tree(root); 
     int pre[] = new int[n]; 

     preOrder_Array_Helper(pre, root, 0); 
     return pre; 
    } 

    private static void preOrder_Array_Helper(int[] pre, BinaryTreeNode<Integer> root, int index) { 
     if (root == null) 
      return;  //-> base case 

     pre[index] = root.data; 
//  index++; 
     if (index == pre.length) { 
      return; 
     } else {  // call for recursion 
      preOrder_Array_Helper(pre, root.left, index + 1); 
      preOrder_Array_Helper(pre, root.right, index + 1); 
     } 
    } 

我理解這個問題，這是由於在遞歸索引（值不斷在覆蓋相同的位置/索引），但我不知道如何解決這個問題，我如何使索引增量。

這可以通過arrayList輕鬆完成，但我想用數組來完成。

Answer 1

可以最後更新指數回報爲方法的結果，並在遞歸調用中使用它：

private static int preOrder_Array_Helper(int[] pre, BinaryTreeNode<Integer> root, int index) { 
    if (root == null) 
     return index;  //return the same as get 

    pre[index] = root.data; 
    index++; 
    if (index == pre.length) { 
     return index; //return new value after add 
    } else { 
     index = preOrder_Array_Helper(pre, root.left, index); //get last after left branch visit 
     return preOrder_Array_Helper(pre, root.right, index); //use new index in right branch 
    } 
} 

，或者您可以使用List<Integer>來避免所有這些問題，指標管理：

public static List<Integer> preOrder_Array(BinaryTreeNode<Integer> root) { 
    if (root == null) 
     return new ArrayList<>();  // array of 0 size 

    List<Integer> pre = new ArrayList<>(); 

    preOrder_Array_Helper(pre, root); 
    return pre; 
} 

private static void preOrder_Array_Helper(List<Integer> pre, BinaryTreeNode<Integer> root) { 
    if (root == null) 
     return; 

    pre.add(root.data); 
    preOrder_Array_Helper(pre, root.left); 
    preOrder_Array_Helper(pre, root.right); 

}