转换级别顺序遍历到中间遍历一个完整的二叉树

Question

给定数组中一个完整二叉树的级别遍历，如何在给定数组中存储所述树的inorder遍历，而不构建树。 这就是我想出的。

void recurse (int *inp, int size_array, int *output, int iter_a, int &iter_b) 
{ 
    if (iter_a>=size_array) 
     return; 

    recurse (inp,size_array,output,2*iter_a+1,iter_b); 


    output[iter_b] = inp[iter_a]; 
    iter_b++; 


    recurse (inp,size_array,output,2*iter_a+2,iter_b); 

} 

是否存在针对上述问题的就地非递归O（n）解决方案？

Answer 1

这是用于将电平以序而不是就地

private class Entry{ 
    int data; 
    int pos; 

    Entry(int data, int pos){ 
     this.data = data; 
     this.pos = pos; 
    } 
} 

public void convertLevelToInorder(int[] levelOrder){ 

    // nodes are stored from index 1 

    int len = levelOrder.length; 
    int[] inOrder = new int[len]; 

    Stack<Entry> stack = new Stack<Entry>(); 

    int pos = 1; 
    int count = 1; 

    while(!stack.isEmpty() || pos < len){ 

     while(pos < len && levelOrder[pos] != -1){ 
      stack.push(new Entry(levelOrder[pos],pos)); 
      pos = pos*2; 
     } 

     Entry e = stack.pop(); 
     inOrder[count++] = e.data; 
     pos = e.pos*2+1; 
    } 

    for(int i=1;i<len;i++) 
     System.out.print(inOrder[i] + " "); 
    System.out.println(); 
} 

一个迭代解