蓝桥与力扣刷题（108 将有序数组转换成二叉搜索树）

题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 

平衡二叉搜索树。

示例 1：

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

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

解题思路＋代码：

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        /**
        思路：BST(深度优先搜索中的中序遍历--左根右)
        1.判断数组的左右边界，左边界大于右边界时返回null
        2.创建BST方法找到数组的中点
        3.由于数组是升序数组，直接按照二分搜索（小于中点在左子树，大于中点在右子树）的方式来存放到二叉树中
         */

         //这里右边界需要注意数组范围溢出
         return BST(nums,0,nums.length-1);
    }

    public TreeNode BST(int[] nums,int left,int right){
        //数组的左边和右边，升序数组不存在左边大于右边的情况
        if(left > right){
            return null;
        }

        //求数组的中点
        int mid = (left + right) / 2;

        //new一个root对象作为根节点
        TreeNode root = new TreeNode(nums[mid]);

        //存放树的叶节点  root的左边放小于中点的数 root的右边放大于中点的数 
        root.left = BST(nums,left,mid - 1);

        root.right = BST(nums,mid + 1,right);

        return root;
    }
}

总结：解答这道题需要了解数组和搜索二叉树的相关性质。数组转换成搜索二叉树，可以联想到二分查找法，那么首先需要找到数组（题目所给是升序数组，否则需排序）的中点，左右边界相加除以2找到数组中点，中点左边为比中点小的数，右边为比中点大的数。搜索二叉树即为平衡二叉树（BST），可以使用深度优先搜索方法中的中序遍历（左根右），根节点为中点，左子树为比根节点小的数，右边为比根节点大的数。此时，二分查找的数组与平衡二叉树就极为相似，最后只需要将数组遍历后存放到平衡二叉树当中就完成了转换。