二叉树算法中shared_ptr与unique_ptr选型困惑：最大二叉树实现难题

你的问题核心在于混淆了算法辅助结构的作用和unique_ptr的所有权唯一性：栈在这里只是用来跟踪节点的单调序列，不需要持有节点的所有权，但你之前用deque<uTreeNode>存储unique_ptr，导致所有权被多次转移（一会儿给子节点，一会儿又压入栈），最终引发非法的空指针操作。

解决方案：用原始指针存储栈元素，让树结构维护所有权 #

栈只需要保存节点的原始指针（用于遍历和修改关系），而节点的所有权完全由树的父子关系（父节点的left/right unique_ptr）来维护，根节点的所有权最终由返回值持有。这样既符合unique_ptr的设计意图，又能完美适配最大二叉树的算法逻辑。

修改后的代码如下：

using uTreeNode = std::unique_ptr<UniqueTreeNode>;

uTreeNode ConstructMaxTree(const std::vector<int>& v) {
    if (v.empty()) return nullptr;

    std::deque<UniqueTreeNode*> node_stack;
    uTreeNode root;

    for (const int val : v) {
        auto current_node = std::make_unique<UniqueTreeNode>(val);
        auto current_ptr = current_node.get();

        // 弹出所有比当前值小的节点，作为当前节点的左孩子
        while (!node_stack.empty() && node_stack.back()->val < val) {
            current_node->left = std::move(node_stack.back());
            node_stack.pop_back();
        }

        if (!node_stack.empty()) {
            // 当前节点成为栈顶节点的右孩子，转移所有权
            node_stack.back()->right = std::move(current_node);
        } else {
            // 栈为空，当前节点就是根节点，保留所有权
            root = std::move(current_node);
        }

        // 将当前节点的指针压入栈（不转移所有权）
        node_stack.push_back(current_ptr);
    }

    return root;
}

关键细节说明 #

• 所有权流转清晰：
  每个节点的所有权只会被转移一次：要么成为某个父节点的左/右孩子（由父节点的unique_ptr持有），要么作为根节点由root持有。栈中存储的原始指针仅用于算法逻辑，不参与所有权管理，因此不会出现多次移动的冲突。

• 避免空指针问题：
  在移动current_node的所有权之前，先保存其原始指针current_ptr，确保栈中始终存储有效的节点地址。当栈为空时，直接将current_node的所有权转移给root，保证根节点的所有权不会丢失。

• 保持unique_ptr的优势：
  完全不需要引入shared_ptr，避免了引用计数的额外开销，同时严格保证了节点所有权的唯一性，符合RAII原则。

为什么你的原始代码会出错？ #

在你的代码中，执行s.back()->right = move(n)后，n的所有权已经转移给了栈顶节点的right指针，此时n已经变成空的unique_ptr。后续的s.emplace_back(move(n))相当于把一个空指针压入栈，这会导致后续操作访问无效内存，引发未定义行为。

内容的提问来源于stack exchange，提问作者Aradhya