構建二叉搜索樹從預遍歷迭代（不遞歸）

Question

以下是將二叉搜索樹的前序遍歷轉換爲原始樹的代碼。

以下代碼需要一個整數數組，它表示二叉搜索樹的預遍歷。結構樹的根被返回。

struct Node* constructTree(int pre[], int size) 
{ 
    stack<struct Node* > s; 
    int i; 
    struct Node* root=newNode(pre[0]); 
    struct Node* temp; 
    struct Node* top_node; 
    s.push(root); 
    for(i=1;i<size;i++) 
    { 
     temp=NULL; 
     while(!s.empty()&&pre[i]>(s.top()->data)) 
      { 
       temp=s.top(); 
       s.pop(); 
      } 
      if(temp==NULL) 
      { 
       top_node=s.top(); 
       top_node->left=newNode(pre[i]); 
       s.push(top_node->left); 
      }else 
      { 
       temp->right=newNode(pre[i]); 
       s.push(temp->right); 
      } 
    } 


    return root; 
} 

來源：http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversal-set-2/

我聽不太懂這個代碼。任何人可以幫助我瞭解以下內容：

1. 在任何給定的迭代，被指向存儲在堆棧中，相對於當前值什麼樣的價值觀出由pre[i]

2. 是否有任何其他的迭代方法從給定的前序遍歷構造BST？

謝謝。

Answer 1

在構建包含pre[i]的節點的迭代之後，堆棧包含頂部的該節點，在該迭代之下，其具有剛好一個子節點的最根節點的祖先從頂部到底部存儲。