Medium

题目描述

给你一个二叉搜索树的根节点 root，返回一个 平衡的 二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多个构造方法，请你返回任意一种。

如果一个二叉搜索树中，每个节点的两个子树的深度差不超过 1，我们就称这个二叉搜索树是 平衡的。

示例 1：

输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2] 也是一个可行的构造方案。

示例 2：

输入：root = [2,1,3]
输出：[2,1,3]

提示：

  • 树节点的数目在 [1, 10^4] 范围内。
  • 1 <= Node.val <= 10^5

解题思路

这道题的核心思路是先将二叉搜索树转换为有序数组，然后利用分治思想重新构造平衡的二叉搜索树。

解题步骤：

  1. 中序遍历获取有序数组：由于二叉搜索树的中序遍历结果是有序的，我们首先对原树进行中序遍历，将所有节点值存储在数组中。

  2. 分治构造平衡树：有了有序数组后，我们可以用分治的方法构造平衡二叉搜索树：

    • 选择数组中间元素作为根节点
    • 左半部分递归构造左子树
    • 右半部分递归构造右子树

这样构造出的树保证是平衡的，因为我们每次都选择中间元素作为根，使得左右子树的节点数量差最多为1。

时间复杂度分析：

  • 中序遍历：O(n)
  • 构造新树：O(n)
  • 总时间复杂度：O(n)

空间复杂度分析：

  • 存储有序数组：O(n)
  • 递归调用栈：O(log n)
  • 总空间复杂度：O(n)

这是一个经典的"先解构再重构"的思路，充分利用了二叉搜索树的性质和分治思想。

代码实现

class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        vector<int> values;
        inorder(root, values);
        return buildBalancedBST(values, 0, values.size() - 1);
    }
    
private:
    void inorder(TreeNode* node, vector<int>& values) {
        if (!node) return;
        inorder(node->left, values);
        values.push_back(node->val);
        inorder(node->right, values);
    }
    
    TreeNode* buildBalancedBST(vector<int>& values, int left, int right) {
        if (left > right) return nullptr;
        
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(values[mid]);
        root->left = buildBalancedBST(values, left, mid - 1);
        root->right = buildBalancedBST(values, mid + 1, right);
        
        return root;
    }
};

class Solution:
    def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def inorder(node):
            if not node:
                return []
            return inorder(node.left) + [node.val] + inorder(node.right)
        
        def build_balanced_bst(values, left, right):
            if left > right:
                return None
            
            mid = (left + right) // 2
            root = TreeNode(values[mid])
            root.left = build_balanced_bst(values, left, mid - 1)
            root.right = build_balanced_bst(values, mid + 1, right)
            
            return root
        
        values = inorder(root)
        return build_balanced_bst(values, 0, len(values) - 1)

public class Solution {
    public TreeNode BalanceBST(TreeNode root) {
        var values = new List<int>();
        Inorder(root, values);
        return BuildBalancedBST(values, 0, values.Count - 1);
    }
    
    private void Inorder(TreeNode node, List<int> values) {
        if (node == null) return;
        Inorder(node.left, values);
        values.Add(node.val);
        Inorder(node.right, values);
    }
    
    private TreeNode BuildBalancedBST(List<int> values, int left, int right) {
        if (left > right) return null;
        
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(values[mid]);
        root.left = BuildBalancedBST(values, left, mid - 1);
        root.right = BuildBalancedBST(values, mid + 1, right);
        
        return root;
    }
}

var balanceBST = function(root) {
    const inorder = (node, values) => {
        if (!node) return;
        inorder(node.left, values);
        values.push(node.val);
        inorder(node.right, values);
    };
    
    const buildBalancedBST = (values, left, right) => {
        if (left > right) return null;
        
        const mid = Math.floor((left + right) / 2);
        const root = new TreeNode(values[mid]);
        root.left = buildBalancedBST(values, left, mid - 1);
        root.right = buildBalancedBST(values, mid + 1, right);
        
        return root;
    };
    
    const values = [];
    inorder(root, values);
    return buildBalancedBST(values, 0, values.length - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)中序遍历O(n) + 构造新树O(n)
空间复杂度O(n)存储有序数组O(n) + 递归栈O(log n)