使用 std::unique_ptr 反转二叉树

Question

我很擅长处理反转二叉树，使用原始指针，但我在尝试使用 unique_ptrs 时遇到了困难。

我有一个 TreeNode class 定义如下：

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

关于您的代码的一些评论。

如果您开始在内部使用智能指针，请不要 return 原始指针。
考虑实现 struct TreeNode.

使用 std::unique_ptr 反转二叉树

Inverting Binary Tree with std::unique_ptr

c++

binary-tree

smart-pointers

unique-ptr