Инвертирование двоичного дерева с помощью std :: unique_ptr

Question

Мне довольно удобно иметь дело с инвертированием двоичного дерева, с использованием необработанных указателей, но я пытаюсь сделать это с unique_ptrs.

У меня есть класс TreeNode, определенный следующим образом:

template<typename T>
struct TreeNode {
    T val;
    unique_ptr<TreeNode<T>> left, right;
};

В настоящее время у меня есть эта функция для инвертирования двоичного дерева:

TreeNode<int>* InvertTree(const unique_ptr<TreeNode<int>>& root) {
    if (root == nullptr) {
        return nullptr;
    }
    auto left = InvertTree(root->left);
    auto right = InvertTree(root->right);
    root->left = make_unique<TreeNode<int>>(right);
    root->right = make_unique<TreeNode<int>>(left);

    return root.get();
}

Это как это должно быть сделано? Какой лучший способ пойти по этому поводу?

Answer 1

Что вам на самом деле нужно, так это swap указатели. unique_ptr не позволяет копировать, но это не требуется в вашем случае: каждое обращение может быть сделано на месте. Попробуйте поменять местами два поддерева:

std::swap(root->left, root->right);

Если вам нужно сделать перевернутую копию, попробуйте что-то вроде этого:

unique_ptr<TreeNode<int>> InvertTree(const unique_ptr<const TreeNode<int>>& node) {
    unique_ptr<TreeNode<int>> inverted_node;
    if (node != nullptr) {
        inverted_node.left = InvertTree(node->right);
        inverted_node.right = InvertTree(node->left);
    }
    return inverted_node;
}

Некоторые комментарии относительно вашего кода.

1. Не возвращайте необработанные указатели, если вы начали работать с интеллектуальными указателями внутри.

2. Рассмотрите возможность реализации конструктора вашего struct TreeNode.