C++根据二叉树的中序遍历替换节点值

假设二叉树的节点结构体定义如下：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

中序遍历二叉树，可以得到一个有序序列。如果我们想要将二叉树中所有节点的值替换为该值在有序序列中的下一个值，可以按照以下步骤进行：

1. 对二叉树进行中序遍历，将值存储在一个数组中。
2. 对数组进行排序，得到有序序列。
3. 再次对二叉树进行中序遍历，对每个节点的值进行替换。

代码如下：

void inorder(TreeNode* root, vector<int>& vals) {
    if (!root) return;
    inorder(root->left, vals);
    vals.push_back(root->val);
    inorder(root->right, vals);
}

void replace(TreeNode* root, vector<int>& vals, int& i) {
    if (!root) return;
    replace(root->left, vals, i);
    root->val = vals[i++];
    replace(root->right, vals, i);
}

void replaceInorder(TreeNode* root) {
    vector<int> vals;
    inorder(root, vals);
    sort(vals.begin(), vals.end());
    int i = 0;
    replace(root, vals, i);
}

注意，该算法的时间复杂度为 $O(n\log n)$，其中 $n$ 是节点个数，因为需要对数组进行排序。如果使用哈希表等数据结构，可以将时间复杂度优化到 $O(n)$。