# 「力扣」第 897 题：递增顺序查找树（中等）
说明：
- 本题 官方题解 (opens new window) 我参与了编写，因此内容与官方题解有重合的地方；
- 本文有幻灯片，在算法吧上不能正常显示，大家可以在 官方题解 (opens new window) 上观看。
# 题目描述
给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
示例 1：
输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
示例 2：
输入：root = [5,1,7]
输出：[1,null,5,null,7]
提示：
- 树中节点数的取值范围是
[1, 100] 0 <= Node.val <= 1000
# 方法一：先中序遍历，再生成新的树
算法
题目要求我们返回按照中序遍历的结果改造而成的、只有右节点的 等价 二叉查找树。提示中说：每个节点具有唯一值。因此我们可以：
- 先对输入的二叉查找树执行中序遍历，将结果保存到一个列表中；
- 然后根据列表中的节点值，创建等价的，只含有右节点的二叉查找树，其过程等价于：根据数组创建一个链表。
代码
class Solution {
public TreeNode increasingBST(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
TreeNode dummyNode = new TreeNode(-1);
TreeNode currNode = dummyNode;
for (int value: res) {
currNode.right = new TreeNode(value);
currNode = currNode.right;
}
return dummyNode.right;
}
public void inorder(TreeNode node, List<Integer> res) {
if (node == null) {
return;
}
inorder(node.left, res);
res.add(node.val);
inorder(node.right, res);
}
}
复杂度分析
- 时间复杂度：
。其中 是二叉查找树的节点总数。 - 空间复杂度：
，保存二叉查找树的所有节点的值需要长度为 的列表。
# 方法二：在中序遍历的过程中改变节点指向
方法一需要遍历一次二叉查找树以后，然后再创建新的等价的二叉查找树。事实上，还可以遍历一次输入二叉查找树，在遍历的过程中改变结点指向以满足题目的要求。
具体来说，在中序遍历的时候，修改结点指向就可以实现。具体地，当我们遍历到一个节点时，把它的左孩子设为空，并将其本身作为上一个遍历到的节点的右孩子。这里需要有一些想象能力。递归遍历的过程中，由于递归函数的调用栈保存了节点的引用，使得上述操作可以实现。下面的幻灯片展示了这样的过程，请见 官方题解 (opens new window)。
代码
class Solution {
private TreeNode resNode;
public TreeNode increasingBST(TreeNode root) {
TreeNode dummyNode = new TreeNode(-1);
resNode = dummyNode;
inorder(root);
return dummyNode.right;
}
public void inorder(TreeNode node) {
if (node == null) {
return;
}
inorder(node.left);
// 在中序遍历的过程中修改结点指向
resNode.right = node;
node.left = null;
resNode = node;
inorder(node.right);
}
}
复杂度分析
- 时间复杂度：
。其中 是二叉查找树的节点总数。 - 空间复杂度：
，保存二叉查找树的所有节点的值需要长度为 的列表。
作者：liweiwei1419 链接：https://suanfa8.com/binary-search-tree/solutions/0897-increasing-order-search-tree 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。