如何使用級別順序遍歷序列構造二叉樹

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