LeetCode_二叉搜索树_简单_108.将有序数组转换为二叉搜索树

拼搏现实的明天。 2023-10-06 23:01 62阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

**示例 1：**  
![在这里插入图片描述][8ba80fbb1b0f465cb1946fc8d150275b.png]  
输入：nums = \[-10,-3,0,5,9\]  
输出：\[0,-3,9,-10,null,5\]  
解释：\[0,-10,5,null,-3,null,9\] 也将被视为正确答案：  
![在这里插入图片描述][ab02725c8e9046f28f517c90b8ccf9b9.png]  
**示例 2：**  
![在这里插入图片描述][df2ff65f4fa04266acf6d6314df93737.png]  
输入：nums = \[1,3\]  
输出：\[3,1\]  
解释：\[1,null,3\] 和 \[3,1\] 都是高度平衡二叉搜索树。

**提示：**  
1 <= nums.length <= 104  
\-104 <= nums\[i\] <= 104  
nums 按严格递增顺序排列

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree

## 2.思路 ##

（1）递归构造  
二叉树的构造过程大致为先：**构造根节点，然后递归构建左右子树**。而一个有序数组对于二叉搜索树来说就是其中序遍历结果，根节点在数组中心，数组左侧是左子树元素，右侧是右子树元素。

相关题目：  
[LeetCode\_二叉树\_中等\_105.从前序与中序遍历序列构造二叉树][LeetCode_105.]  
[LeetCode\_二叉树\_中等\_106.从中序与后序遍历序列构造二叉树][LeetCode_106.]

## 3.代码实现（Java） ##

//思路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) {
        
            return build(nums, 0, nums.length - 1);
        }
    	
    	//将 nums[left...right] 转换为一棵高度平衡二叉搜索树
        public TreeNode build(int[] nums, int left, int right) {
        
            if (left > right) {
        
            	// nums[left...right] 为空
                return null;
            }
            //构造根节点
            int mid = (left + right) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            //递归构造左子树
            root.left = build(nums, left, mid - 1);
            //递归构造右子树
            root.right = build(nums, mid + 1, right);
            return root;
        }
    }

[8ba80fbb1b0f465cb1946fc8d150275b.png]: https://img-blog.csdnimg.cn/8ba80fbb1b0f465cb1946fc8d150275b.png
[ab02725c8e9046f28f517c90b8ccf9b9.png]: https://img-blog.csdnimg.cn/ab02725c8e9046f28f517c90b8ccf9b9.png
[df2ff65f4fa04266acf6d6314df93737.png]: https://img-blog.csdnimg.cn/df2ff65f4fa04266acf6d6314df93737.png
[LeetCode_105.]: https://xgqngu.blog.csdn.net/article/details/123727823
[LeetCode_106.]: https://blog.csdn.net/weixin_43004044/article/details/123747145