algorithm - 实现迭代单栈二叉树复制函数

Question

作为一个思维练习，我正在尝试实现一个迭代树(二叉或二叉搜索树)复制函数。

据我了解，它可以轻松实现:

• 只有一个堆栈
• 不使用包装器(包含对副本和原始节点的引用)
• 没有节点引用它的父节点(节点中的父引用是否与树的真实定义相反 [我认为这是一个 DAG]？)

我已经编写了满足上述约束的逆向的不同实现，但我不确定如何使用这些约束来解决问题。

我在算法 4/e 中没有看到任何东西，也没有在网上看到任何东西(除了关于它是多么微不足道的陈述)。我考虑过使用当前/先前 var 的顺序和后顺序中的概念，但我没有看到在弹出堆栈时准确跟踪的方法。我也简单地考虑过 HashMap ，但我觉得这仍然只是额外的存储空间，就像额外的堆栈一样。

对于理解我没有看到的方法背后的概念/习语的任何帮助，我们都非常感激。

提前致谢。

编辑:

到目前为止我已经尝试过的一些请求。这是 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))

编辑:
如果您想查看工作代码，我创建了一个 implementation在 python 中。