LeetCode 1382. 将二叉搜索树变平衡：中序遍历与有序数组重建

LeetCode 1382. 将二叉搜索树变平衡

Problem: 1382. 将二叉搜索树变平衡

1. 整体思路

核心问题

我们需要将一棵可能高度不平衡的二叉搜索树（BST），转换成一棵高度平衡的二叉搜索树。

算法逻辑

1. 中序遍历 (In-order Traversal)：
   • 二叉搜索树的特性：通过中序遍历（左 -> 根 -> 右）可以得到一个升序的节点值序列。
   • 我们将原 BST 的所有节点值按照中序遍历的顺序存入一个 List<Integer> 中。
   • 这一步将树结构转化为了有序数组结构，消除了原本的树结构信息。
2. 有序数组转平衡 BST (Reconstruction)：
   • 这是一个经典问题（LeetCode 108. 将有序数组转换为二叉搜索树）。
   • 策略：为了让生成的 BST 尽可能平衡，我们应该总是选择数组的中间元素作为根节点。
   • 这样，数组被均分为左右两半，左半部分构建左子树，右半部分构建右子树。
   • 这个过程递归进行，直到数组范围为空。
   • 由于每次都取中点，左右子树的高度差最多为 1，从而保证了结果是一棵高度平衡的 BST。

2. 完整代码

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        // 1. 中序遍历获取升序数组
        List<Integer> nums = inorderTraversal(root);
        // 2. 将有序数组转换为平衡二叉搜索树
        return sortedArrayToBST(nums);
    }

    // 中序遍历辅助方法
    private List<Integer> inorderTraversal(TreeNode node) {
        List<Integer> ans = new ArrayList<>();
        dfs(ans, node);
        return ans;
    }

    
       {
         (node == ) {
            ;
        }
        dfs(ans, node.left);
        ans.add(node.val);
        dfs(ans, node.right);
    }

    
     TreeNode  {
        
         buildBST(nums, , nums.size());
    }

    
    
    
     TreeNode  {
        
         (left == right) {
             ;
        }
        
        
           (left + right) >>> ;
        
        
        
          (nums.get(m), buildBST(nums, left, m), buildBST(nums, m + , right));
    }
}