公司网站需要备案吗,免费发帖论坛大全,招聘网站是怎么做推广,wordpress iis速度慢108. 将有序数组转换为二叉搜索树 题目描述 给你一个整数数组 nums #xff0c;其中元素已经按 升序 排列#xff0c;请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1#xff1a… 108. 将有序数组转换为二叉搜索树 题目描述 给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 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可以使得树保持平衡。如果数组长度是奇数则根节点的选择是唯一的如果数组长度是偶数则可以选择中间位置左边的数字作为根节点或者选择中间位置右边的数字作为根节点选择不同的数字作为根节点则创建的平衡二叉搜索树也是不同的。 确定平衡二叉搜索树的根节点之后其余的数字分别位于平衡二叉搜索树的左子树和右子树中左子树和右子树分别也是平衡二叉搜索树因此可以通过递归的方式创建平衡二叉搜索树。 递归的基准情形是平衡二叉搜索树不包含任何数字此时平衡二叉搜索树为空。 在给定中序遍历序列数组的情况下每一个子树中的数字在数组中一定是连续的因此可以通过数组下标范围确定子树包含的数字下标范围记为 \([\textit{left}, \textit{right}]\)。对于整个中序遍历序列下标范围从 \(\textit{left}0\) 到 \(\textit{right}\textit{nums}.\text{length}-1\)。当 \(\textit{left}\textit{right}\) 时平衡二叉搜索树为空。 以下三种方法中方法一总是选择中间位置左边的数字作为根节点方法二总是选择中间位置右边的数字作为根节点方法三是方法一和方法二的结合选择任意一个中间位置数字作为根节点。 方法一中序遍历总是选择中间位置左边的数字作为根节点 选择中间位置左边的数字作为根节点则根节点的下标为 \(\textit{mid}(\textit{left}\textit{right})/2\)此处的除法为整数除法。 时间复杂度\(O(n)\)其中 \(n\) 是数组的长度。每个数字只访问一次。 空间复杂度\(O(\log n)\)其中 \(n\) 是数组的长度。空间复杂度不考虑返回值因此空间复杂度主要取决于递归栈的深度递归栈的深度是 \(O(\log n)\)。 Python3 class Solution:def sortedArrayToBST(self, nums: List[int]) - TreeNode:def helper(left, right):if left right:return None# 总是选择中间位置左边的数字作为根节点mid (left right) // 2root TreeNode(nums[mid])root.left helper(left, mid - 1)root.right helper(mid 1, right)return rootreturn helper(0, len(nums) - 1) C class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {return helper(nums, 0, nums.size() - 1);}TreeNode* helper(vectorint nums, int left, int right) {if (left right) {return nullptr;}// 总是选择中间位置左边的数字作为根节点int mid (left right) / 2;TreeNode* root new TreeNode(nums[mid]);root-left helper(nums, left, mid - 1);root-right helper(nums, mid 1, right);return root;}
}; 方法二中序遍历总是选择中间位置右边的数字作为根节点 选择中间位置右边的数字作为根节点则根节点的下标为 \(\textit{mid}(\textit{left}\textit{right}1)/2\)此处的除法为整数除法。 时间复杂度\(O(n)\)其中 \(n\) 是数组的长度。每个数字只访问一次。 空间复杂度\(O(\log n)\)其中 \(n\) 是数组的长度。空间复杂度不考虑返回值因此空间复杂度主要取决于递归栈的深度递归栈的深度是 \(O(\log n)\)。 Python3 class Solution:def sortedArrayToBST(self, nums: List[int]) - TreeNode:def helper(left, right):if left right:return None# 总是选择中间位置右边的数字作为根节点mid (left right 1) // 2root TreeNode(nums[mid])root.left helper(left, mid - 1)root.right helper(mid 1, right)return rootreturn helper(0, len(nums) - 1) C class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {return helper(nums, 0, nums.size() - 1);}TreeNode* helper(vectorint nums, int left, int right) {if (left right) {return nullptr;}// 总是选择中间位置右边的数字作为根节点int mid (left right 1) / 2;TreeNode* root new TreeNode(nums[mid]);root-left helper(nums, left, mid - 1);root-right helper(nums, mid 1, right);return root;}
}; 方法三中序遍历选择任意一个中间位置数字作为根节点 选择任意一个中间位置数字作为根节点则根节点的下标为 \(\textit{mid}(\textit{left}\textit{right})/2\)和 \(\textit{mid}(\textit{left}\textit{right}1)/2\) 两者中随机选择一个此处的除法为整数除法。 时间复杂度\(O(n)\)其中 \(n\) 是数组的长度。每个数字只访问一次。 空间复杂度\(O(\log n)\)其中 \(n\) 是数组的长度。空间复杂度不考虑返回值因此空间复杂度主要取决于递归栈的深度递归栈的深度是 \(O(\log n)\)。 Python3 class Solution:def sortedArrayToBST(self, nums: List[int]) - TreeNode:def helper(left, right):if left right:return None# 选择任意一个中间位置数字作为根节点mid (left right randint(0, 1)) // 2root TreeNode(nums[mid])root.left helper(left, mid - 1)root.right helper(mid 1, right)return rootreturn helper(0, len(nums) - 1) C class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {return helper(nums, 0, nums.size() - 1);}TreeNode* helper(vectorint nums, int left, int right) {if (left right) {return nullptr;}// 选择任意一个中间位置数字作为根节点int mid (left right rand() % 2) / 2;TreeNode* root new TreeNode(nums[mid]);root-left helper(nums, left, mid - 1);root-right helper(nums, mid 1, right);return root;}
};
