如何使用级别顺序遍历序列构造二叉树

Question

如何使用级别顺序遍历序列构造二叉树，例如从序列{1,2,3，＃，＃，4，＃，＃，5 }，我们可以构造一个二叉树这样的：

 1 
    /\ 
    2 3 
    /
    4 
     \ 
     5 

其中“＃”表示下文有节点存在的路径终止。

最后我用C++实现范忠算法

struct TreeNode 
{ 
    TreeNode *left; 
    TreeNode *right; 
    int val; 

    TreeNode(int x): left(NULL), right(NULL), val(x) {} 
}; 
TreeNode *build_tree(char nodes[], int n) 
{ 
    TreeNode *root = new TreeNode(nodes[0] - '0'); 
    queue<TreeNode*> q; 
    bool is_left = true; 
    TreeNode *cur = NULL; 
    q.push(root); 

    for (int i = 1; i < n; i++) { 
     TreeNode *node = NULL; 
     if (nodes[i] != '#') { 
      node = new TreeNode(nodes[i] - '0'); 
      q.push(node); 
     } 

     if (is_left) { 
      cur = q.front(); 
      q.pop(); 
      cur->left = node; 
      is_left = false; 
     } else { 
      cur->right = node; 
      is_left = true; 
     } 
    } 

    return root; 
} 

Answer 1

假设使用数组int[]data有从零开始的索引，我们有一个简单的功能，让孩子们：

• 左子

  int getLeftChild(int index){ 
      if(index*2 + 1 >= data.length) 
       return -1;// -1 Means out of bound 
      return data[(index*2) + 1]; 
  } 
  

• 右孩子

  int getRightChild(int index){ 
      if(index*2 + 2 >= data.length) 
       return -1;// -1 Means out of bound   
      return data[(index*2) + 2]; 
  } 
  

编辑： 好了，通过维持一个队列，我们​​可以建立这种二叉树。

我们使用队列来维护那些尚未处理的节点。

使用变量计数来跟踪为当前节点添加的子级数。

首先，创建一个根节点，将其分配为当前节点。 因此，从索引1开始（索引0是根），因为计数为0，我们将此节点添加为当前节点的左侧子节点。 增加计数。如果此节点不是'＃'，请将其添加到队列中。

移动到下一个索引，计数为1，因此我们将此作为当前节点的右侧子节点，将计数重置为0并更新当前节点（通过将当前节点分配为队列中的第一个元素）。如果此节点不是'＃'，请将其添加到队列中。

 int count = 0; 
    Queue q = new Queue(); 
    q.add(new Node(data[0]); 
    Node cur = null; 
    for(int i = 1; i < data.length; i++){ 
     Node node = new Node(data[i]); 
     if(count == 0){ 
      cur = q.dequeue();   
     } 
     if(count==0){ 
      count++; 
      cur.leftChild = node; 
     }else { 
      count = 0; 
      cur.rightChild = node; 
     } 
     if(data[i] != '#'){ 
      q.enqueue(node); 
     } 
    }  



    class Node{ 
     int data; 
     Node leftChild, rightChild; 
    }