C++实现中序遍历重排为增序二叉树

本资源主要讨论的是如何通过编程实现将一棵二叉搜索树（BST）重新排列成一个严格递增的二叉搜索树（Increasing Order Search Tree，即每个节点值都大于其左子树的所有节点值，且等于或小于其右子树的所有节点值）。问题来自LeetCode平台，题目编号为**Increasing Order Search Tree**。 方法一：中序遍历结合队列 该方法的核心思想是利用中序遍历的特性，即左根右的访问顺序。首先，对原始BST进行中序遍历，遍历时将节点按照遍历顺序依次存入队列`qtn`。这样，队列中的第一个元素就是新树的根节点。接下来，每次从队列中取出节点并将其右子节点入队，以保持右侧子树的递增顺序。遍历结束后，队列中剩余的节点将成为新树的右子树。 ```cpp class Solution { private: queue<TreeNode*> qtn; void __midOrder(TreeNode* node) { if (node == NULL) { return; } // 中序遍历的左-根-右顺序 __midOrder(node->left); qtn.push(node); __midOrder(node->right); } public: TreeNode* increasingBST(TreeNode* root) { __midOrder(root); // 重建新的二叉搜索树 TreeNode* newRoot = qtn.front(); // 新树的根 TreeNode* prev = nullptr; while (!qtn.empty()) { TreeNode* node = qtn.front(); qtn.pop(); // 设置新节点的左指针为空，以便于后续节点插入右子树 node->left = nullptr; // 如果有前驱节点，设置当前节点为前驱节点的右子节点 if (prev) { prev->right = node; } else { newRoot = node; // 如果是第一个节点，它本身就是新树的根 } prev = node; } return newRoot; } }; ``` 方法二与方法三：直接在中序遍历过程中构建 方法二是在中序遍历的过程中，直接根据遍历顺序建立链表，无需额外的队列辅助。由于题目中提到的方法三还未完成，这里假设它可能采用迭代方式来实现，但原理类似，即遍历过程中不断更新节点的左右指针，使得遍历过程既实现了中序，又构建了新树结构。 总结： - 问题要求将给定的二叉搜索树重新排列成递增顺序，核心在于中序遍历的运用，通过队列或者迭代的方式确保节点按升序排列。 - 使用C++中的`TreeNode`结构表示树节点，`Solution`类包含了私有成员`qtn`（队列）以及`__midOrder`函数用于中序遍历。 - `increasingBST`函数是公共接口，接收原始BST的根节点，返回新的递增BST的根节点。 - 在实际操作中，先执行中序遍历并将节点放入队列，然后根据队列元素构建新的递增BST，保持节点的右子节点指向下一个待处理的节点，直到队列为空。 通过以上分析，我们可以看到解决这个问题的关键在于理解中序遍历的顺序和如何通过数据结构（如队列或迭代）实现这一转换。这种方法在面试或者算法竞赛中常被用来考察对递归和数据结构的理解，以及在实际问题中的应用能力。