實現迭代單棧二叉樹複製函數

Question

作爲一種思考練習，我試圖實現一個迭代樹（二叉或二叉搜索樹）複製函數。

這是我的理解，它可以平凡實現：

• 與單一堆棧
• 不使用包裝（包含要複製和原節點的引用）
• ，而無需一個節點引用它的父節點（父節點中的父節點是否與樹的真正定義相反[我認爲它是DAG]？）

我寫了不同的實現滿足上述約束的逆過程，但我不確定如何用約束來解決問題。

我在算法4/e中沒有看到任何東西，也沒有在線看到任何東西（除了它是多麼微不足道的陳述之外）。我考慮使用當前/前一個var的順序和後序概念，但是我沒有看到彈出堆棧時精確跟蹤的方法。我還簡要地考慮了哈希映射，但我覺得這仍然只是額外的存儲，就像額外的堆棧。

任何幫助理解我沒有看到的方法背後的概念/成語是感激地收到。

在此先感謝。

編輯：

什麼，我到目前爲止已經試過一些請求。這裏是2堆棧解決方案，我認爲它應該能夠最輕鬆地變成1堆棧。

它是用C++編寫的。我對這門語言很陌生（但不是編程），並且使用C++ Primer 5/e（Lippman，Lajole，Moo）[C++ 11]和互聯網教我自己。如果從語言角度來看任何代碼都是錯誤的，請告訴我（雖然我知道Code Review Stack Exchange是進行實際評論的地方）。

我有一個由代碼的其他部分使用的模板節點。

template<typename T> 
struct Node; 

typedef Node<std::string> tree_node; 
typedef std::shared_ptr<tree_node> shared_ptr_node; 

template<typename T> 
struct Node final { 

public: 
    const T value; 
    const shared_ptr_node &left = m_left; 
    const shared_ptr_node &right = m_right; 

    Node(const T value, const shared_ptr_node left = nullptr, const shared_ptr_node right = nullptr) : value(value), m_left(left), m_right (right) {} 

    void updateLeft(const shared_ptr_node node) { 
     m_left = node; 
    } 

    void updateRight(const shared_ptr_node node) { 
     m_right = node; 
    } 

private: 
    shared_ptr_node m_left; 
    shared_ptr_node m_right; 
}; 

然後2棧實現。

shared_ptr_node iterativeCopy2Stacks(const shared_ptr_node &node) { 

    const shared_ptr_node newRoot = std::make_shared<tree_node>(node->value); 

    std::stack<const shared_ptr_node> s; 
    s.push(node); 

    std::stack<const shared_ptr_node> copyS; 
    copyS.push(newRoot); 

    shared_ptr_node original = nullptr; 
    shared_ptr_node copy = nullptr; 

    while (!s.empty()) { 

     original = s.top(); 
     s.pop(); 

     copy = copyS.top(); 
     copyS.pop(); 

     if (original->right) { 
      s.push(original->right); 

      copy->updateRight(std::make_shared<tree_node>(original->right->value)); 
      copyS.push(copy->right); 
     } 

     if (original->left) { 
      s.push(original->left); 

      copy->updateLeft(std::make_shared<tree_node>(original->left->value)); 
      copyS.push(copy->left); 
     } 
    } 

    return newRoot; 
} 

Answer 1

我不精通C++，所以你必須用僞代碼來解決：

node copy(treenode n): 
    if n == null 
     return null 

    node tmp = clone(n) //no deep clone!!! 

    stack s 
    s.push(tmp) 

    while !s.empty(): 
     node n = s.pop() 

     if n.left != null: 
      n.left = clone(n.left) 
      s.push(n.left) 
     if n.right != null: 
      n.right = clone(n.right) 
      s.push(n.right) 

    return tmp 

注意clone(node)是不深克隆。其基本思想是先從根的淺層克隆開始，然後迭代該節點的所有子節點，並用淺拷貝替換那些節點（仍然引用原始節點），替換那些節點子節點等。此算法遍歷樹以DFS方式。如果你更喜歡BFS（無論什麼原因），你可以用一個隊列來替換堆棧。這個代碼的另一個優點是：它可以通過一些小的改變來改變，以適用於任意樹。

此算法的遞歸版本（如果你喜歡遞歸代碼在我的可怕PROSA）：

node copyRec(node n): 
    if n.left != null: 
     n.left = clone(n.left) 
     copyRec(n.left) 

    if n.right != null: 
     n.right = clone(n.right) 
     copyRec(n.right) 

    return n 

node copy(node n): 
    return copyRec(clone(n)) 

編輯：
如果你想看看運行的代碼，我創建了一個在Python中使用implementation。