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

短命女 2022-12-10 07:06 156阅读 0赞

## 一、题目描述 ##

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

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

示例:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70][]

--------------------

## 二、思路 ##

二叉搜索树，即对于其中任何一个结点node，其左子树上的节点值都小于等于node值，其右子树上的结点都大于等于node值，那么其中序遍历正好就是一个升序数组。

题目要求这棵树是一个平衡树，因此树中任意一个节点左右两个子树的高度差不可以超过1。所以我们可以将数组最中间元素或紧靠中间左右两边的元素（即nums\[length/2\]）作为平衡二叉搜索树的根节点，从0到length/2-1作为左子树，length/2+1到length-1作为右子树。

当然根节点的左右子树依然是一颗平衡二叉搜索树，可以使用递归解决该问题。

给定一个左边界left，右边界right，当left>rigth时返回。每次取nums\[(left+right)/2\]作为当前树的根节点。接着其左边的数用于构造左子树，右边的数用于构造右子树。

该解法的时间复杂度为O(n)，n代表数组的长度，因为每个元素只被访问一次。

空间复杂度为O(logn)，n代表数组的长度，空间复杂度取决于递归的深度。

--------------------

## 三、代码实现 ##

public TreeNode sortedArrayToBST(int[] nums) {
            return recursion(0, nums.length - 1, nums);
        }
    
        public TreeNode recursion(int left, int right, int[] nums) {
            if (left > right) {
                return null;
            }
            //去数组中间或紧靠中间左右两边的数
            int middle = (left + right) / 2;
            //根节点
            TreeNode root = new TreeNode(nums[middle]);
            //左子树
            root.left = recursion(left, middle - 1, nums);
            //右子树
            root.right = recursion(middle + 1, right, nums);
            return root;
        }

提交答案：

![20200924134334761.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTkxOTAz_size_16_color_FFFFFF_t_70]: /images/20221123/b4bddfcb50464bc4a7539c23d5d4da56.png
[20200924134334761.png]: /images/20221123/750e222be3df4deb85342ba6521307ce.png