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

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

• 题目
• 解题思路
• 代码

题目

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

解题思路

这题不是普通的反序列化二叉树，而是要求你生成一颗二叉搜索树。

抓住二叉搜索树这一点，我们可以直接取数组中间的值作为根节点（数组是有序的），来构成一棵树—“一个节点该做的事”。然后剩下的交给递归框架

代码

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

    private TreeNode dfs(int[] nums, int lo, int hi) {
        if (lo > hi) {
            return null;
        } 
        // 以升序数组的中间元素作为根节点 root。
        int mid = lo + (hi - lo) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        // 递归的构建 root 的左子树与右子树。
        root.left = dfs(nums, lo, mid - 1);
        root.right = dfs(nums, mid + 1, hi); 
        return root;
    }
}