二叉树在时间复杂度为on时找到两个最小的权?C语言或C++

在二叉搜索树（BST）中查找两个最小的元素的时间复杂度可以达到O(n)，这是因为最坏的情况下，如果输入数组完全逆序，那么树会退化成一个链表。但是，如果我们维护额外的信息，比如同时跟踪当前遍历路径上遇到的两个最小值，我们可以在平均情况下达到更优的时间复杂度。

在C或C++中，我们可以使用迭代的方式来解决这个问题。首先，创建两个指针`prev`和`curr`，分别指向第一个和第二个最小值。然后，在遍历树的过程中，如果找到一个比`curr`小的节点，更新`prev`和`curr`；如果找到一个比`prev`小但大于等于`curr`的节点，说明找到了新的最小值对，更新`prev`。这种方法的时间复杂度通常被认为是O(h)，其中h是树的高度，对于平衡的二叉搜索树来说，h接近于log n。

以下是C++伪代码示例：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

pair<int, int> findTwoSmallest(TreeNode* root) {
    pair<int, int> result({INT_MAX, INT_MAX});
    TreeNode* prev = nullptr, *curr = root;

    while (curr != nullptr) {
        if (curr->val < result.first) {
            result.second = result.first;
            result.first = curr->val;
        } else if (curr->val < result.second && curr->val > result.first) {
            result.second = curr->val;
        }
        if (curr->left == nullptr) {
            curr = curr->right;
        } else {
            prev = curr;
            curr = curr->left;
        }
    }

    return result;
}