本文共 1766 字，大约阅读时间需要 5 分钟。

领扣LintCode算法问题答案-1359. 有序数组转换为二叉搜索树

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

描述

给定一个数组，其中元素按升序排序，将其转换为高度平衡的BST。

对于这个问题，高度平衡的二叉树被定义为二叉树，其中每个节点的两个子树的深度从不相差超过1。

样例 1：

输入: [-10,-3,0,5,9],输出: [0,-3,9,-10,#,5],解释:针对该数组的其中一个解为 [0,-3,9,-10,null,5], 其对应的平衡BST树如下:      0     / \   -3   9   /   / -10  5

样例 2：

输入: [1,3]输出: [3,1]解释:针对该数组的其中一个解为 [3,1], 其对应的平衡BST树如下:  3 / 1

题解

/** * Definition of TreeNode: * public class TreeNode { *     public int val; *     public TreeNode left, right; *     public TreeNode(int val) { *         this.val = val; *         this.left = this.right = null; *     } * } */public class Solution {
       /**     * @param nums: the sorted array     * @return: the root of the tree     */    public TreeNode convertSortedArraytoBinarySearchTree(int[] nums) {
           // Write your code here.       if (nums == null            || nums.length == 0) {
               return null;        }        int mid = (nums.length - 1) / 2;        TreeNode root = new TreeNode(nums[mid]);        root.left = convertSortedArraytoBinarySearchTree(nums, 0, mid - 1);        root.right = convertSortedArraytoBinarySearchTree(nums, mid + 1, nums.length - 1);        return root;    }    private TreeNode convertSortedArraytoBinarySearchTree(int[] nums, int startIndex, int endIndex) {
           if (startIndex > endIndex            || startIndex < 0            || endIndex >= nums.length) {
               return null;        }        int mid = (startIndex + endIndex) / 2;        TreeNode root = new TreeNode(nums[mid]);        root.left = convertSortedArraytoBinarySearchTree(nums, startIndex, mid - 1);        root.right = convertSortedArraytoBinarySearchTree(nums, mid + 1, endIndex);        return root;    }}

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。

欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。

转载地址：https://le-yi.blog.csdn.net/article/details/108916000 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！