【二叉树】Leetcode 108. 将有序数组转换为二叉搜索树【简单】

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

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

示例1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案

解题思路

将一个有序数组转换为平衡二叉搜索树，可以通过递归方式来实现。

• 1、选择数组的中间元素作为根节点，将其值赋给根节点。
• 2、将数组分成左右两部分，左边部分构成左子树，右边部分构成右子树。
• 3、递归地对左右子数组进行构建平衡二叉搜索树的操作。

Java实现

public class SortedArrayToBST {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        // 选择中间元素作为根节点
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);

        // 递归构建左右子树
        root.left = sortedArrayToBST(nums, start, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, end);

        return root;
    }

    // 测试示例
    public static void main(String[] args) {
        SortedArrayToBST converter = new SortedArrayToBST();

        // 示例数组
        int[] nums = {-10, -3, 0, 5, 9};

        // 转换为二叉搜索树
        TreeNode resultTree = converter.sortedArrayToBST(nums);

        // 打印中序遍历结果验证
        System.out.println("Inorder traversal of the constructed BST:");
        inorderTraversal(resultTree);
    }

    private static void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.val + " ");
            inorderTraversal(root.right);
        }
    }
}

时间空间复杂度

• 时间复杂度：O(n)，其中n是数组的长度，每个元素都需要访问一次。
• 空间复杂度：O(log n)，递归调用栈的深度为树的高度。

算法目录导航栏