Easy

题目描述

给你一个二叉搜索树的根节点 root，请你将其重新排列为一个递增顺序查找树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 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

解题思路

这道题要求将二叉搜索树重新排列成只有右子树的递增链表结构。

核心思路：利用二叉搜索树的中序遍历性质，中序遍历的结果就是递增序列。我们可以通过中序遍历，将节点按顺序连接成只有右子树的链表。

主要解法：

  1. 中序遍历 + 重新构造：先中序遍历收集所有节点值，再构造新的链表结构
  2. 原地修改（推荐）：在中序遍历过程中直接修改树结构，使用一个指针记录当前链表的尾节点

推荐解法详解： 使用原地修改的方法，在中序遍历过程中：

  • 维护一个 prev 指针，指向当前已构造链表的最后一个节点
  • 对于每个访问的节点，将其左子树置空，让 prev 的右子树指向当前节点
  • 更新 prev 为当前节点
  • 使用虚拟头节点简化边界处理

这种方法时间复杂度O(n)，空间复杂度O(h)（递归栈深度）。

代码实现

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode dummy(0);
        prev = &dummy;
        inorder(root);
        return dummy.right;
    }
    
private:
    TreeNode* prev;
    
    void inorder(TreeNode* node) {
        if (!node) return;
        
        inorder(node->left);
        
        node->left = nullptr;
        prev->right = node;
        prev = node;
        
        inorder(node->right);
    }
};

class Solution:
    def increasingBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def inorder(node):
            if not node:
                return
            
            inorder(node.left)
            
            node.left = None
            self.prev.right = node
            self.prev = node
            
            inorder(node.right)
        
        dummy = TreeNode(0)
        self.prev = dummy
        inorder(root)
        return dummy.right

public class Solution {
    private TreeNode prev;
    
    public TreeNode IncreasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
        prev = dummy;
        Inorder(root);
        return dummy.right;
    }
    
    private void Inorder(TreeNode node) {
        if (node == null) return;
        
        Inorder(node.left);
        
        node.left = null;
        prev.right = node;
        prev = node;
        
        Inorder(node.right);
    }
}

var increasingBST = function(root) {
    let prev;
    
    function inorder(node) {
        if (!node) return;
        
        inorder(node.left);
        
        node.left = null;
        prev.right = node;
        prev = node;
        
        inorder(node.right);
    }
    
    const dummy = new TreeNode(0);
    prev = dummy;
    inorder(root);
    return dummy.right;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要访问树中的每个节点一次
空间复杂度O(h)递归栈的深度，h为树的高度，最坏情况下O(n)