当前位置：首页 > news >正文

【力扣热题100】—— Day18.将有序数组转换为二叉搜索树

news 2025/6/28 23:14:11

期末考试完毕，假期学习开始！

—— 25.1.7

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] 都是高度平衡二叉搜索树。

提示：

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

方法一递归

思路与算法

二叉搜索树的性质：对于树中的每个节点：① 若其左子树不为空，则左子树上所有节点的值均小于该节点的值。② 若其右子树不为空，则右子树上所有节点的值均大于该节点的值。③ 它的左子树和右子树也都是二叉搜索树

将数组/列表长度不断进行二分，使得数组/列表长度的1/2处(向下取整)作为树和每个子树的根节点，而小于数组/列表长度一半的和大于数组/列表长度一半的分别作为左子树和右子树，由二叉搜索树的性质，不断进行递归，最终使得数组/列表为空时停止递归，这样就可以得到由数组/列表转换后的二叉搜索树

Python实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:if not nums:return Nonem = len(nums) // 2return TreeNode(nums[m], self.sortedArrayToBST(nums[:m]), self.sortedArrayToBST(nums[m + 1:]))

Java实现

/*** 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 dfs(nums, 0, nums.length);}private TreeNode dfs(int[] nums, int left, int right) {if (left == right) {return null;}int m = (left + right) / 2;return new TreeNode(nums[m], dfs(nums, left, m), dfs(nums, m + 1, right));}
}