威客网站系统关键词搜索

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

                                —— 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));}
}

---

注：

① Java中的数组数据结构，在Python中使用列表的数据结构 

② python中递归的遍历，支持列表传参时索引使用 ：m 和 m+1：

：m指的是从列表起始位置遍历到m-1的位置，m+1：指的是从m+1的位置遍历到列表尾部，列表遍历时的索引是左闭右开

③ Java由于遍历时不支持数组传参时直接的切片操作，所以我们创建一个private私有权限的递归方法，然后最后将结果传给主函数，由主函数进行返回