将有序数组转换为二叉搜索树

108.将有序数组转换为二叉搜索树

题意

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

平衡二叉树：是指该树所有节点的左右子树的深度相差不超过 1。

思路

由于 BST 的中序遍历是升序的，所以本题等同于根据中序遍历的序列建立二叉搜索树。

因为本题要求高度平衡，所以选择序列的中间值作为根节点，不断二分递归建立左子树和右子树。

代码

class Solution {
    TreeNode dfs(int[] nums, int l, int r) {
        if (l > r) return null;

        // 以升序数组的中间元素作为根节点
        int mid = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[mid]);

        // 递归的构建左子树与右子树
        root.left = dfs(nums, l, mid - 1);
        root.right = dfs(nums, mid + 1, r);
        
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }
}