网站所有人,网站制作大概费用,wordpress文章点击次数插件,网站建设可行性分析报告模板期末考试完毕#xff0c;假期学习开始#xff01; —— 25.1.7 108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums #xff0c;其中元素已经按 升序 排列#xff0c;请你将其转换为一棵平衡二叉搜索树。
示例 1#xff1a; 输入#xff1a;nums [-10,-3,0,5,9]
… 期末考试完毕假期学习开始 —— 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] 104nums 按 严格递增 顺序排列 方法一 递归
思路与算法
二叉搜索树的性质对于树中的每个节点① 若其左子树不为空则左子树上所有节点的值均小于该节点的值。② 若其右子树不为空则右子树上所有节点的值均大于该节点的值。③ 它的左子树和右子树也都是二叉搜索树
将数组/列表长度不断进行二分使得数组/列表长度的1/2处(向下取整)作为树和每个子树的根节点而小于数组/列表长度一半的和大于数组/列表长度一半的分别作为左子树和右子树由二叉搜索树的性质不断进行递归最终使得数组/列表为空时停止递归这样就可以得到由数组/列表转换后的二叉搜索树 Python实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# 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 和 m1
m指的是从列表起始位置遍历到m-1的位置m1指的是从m1的位置遍历到列表尾部列表遍历时的索引是左闭右开
③ Java由于遍历时不支持数组传参时直接的切片操作所以我们创建一个private私有权限的递归方法然后最后将结果传给主函数由主函数进行返回
