转换树的序阵列（递归）

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); 

}