上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 3.4 MB, 提交时间: 2023-10-28 12:51:53
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedArrayToBST(nums []int) *TreeNode {
rand.Seed(time.Now().UnixNano())
return helper(nums, 0, len(nums) - 1)
}
func helper(nums []int, left, right int) *TreeNode {
if left > right {
return nil
}
// 选择任意一个中间位置数字作为根节点
mid := (left + right + rand.Intn(2)) / 2
root := &TreeNode{Val: nums[mid]}
root.Left = helper(nums, left, mid - 1)
root.Right = helper(nums, mid + 1, right)
return root
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.3 MB, 提交时间: 2023-10-28 12:51:36
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedArrayToBST(nums []int) *TreeNode {
return helper(nums, 0, len(nums) - 1)
}
func helper(nums []int, left, right int) *TreeNode {
if left > right {
return nil
}
// 总是选择中间位置右边的数字作为根节点
mid := (left + right + 1) / 2
root := &TreeNode{Val: nums[mid]}
root.Left = helper(nums, left, mid - 1)
root.Right = helper(nums, mid + 1, right)
return root
}
python3 解法, 执行用时: 56 ms, 内存消耗: 17.6 MB, 提交时间: 2023-10-28 12:50:49
# 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]) -> TreeNode:
def helper(left, right):
if left > right:
return None
# 选择任意一个中间位置数字作为根节点
mid = (left + right + randint(0, 1)) // 2
root = TreeNode(nums[mid])
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(nums) - 1)
def sortedArrayToBST2(self, nums: List[int]) -> TreeNode:
def helper(left, right):
if left > right:
return None
# 总是选择中间位置右边的数字作为根节点
mid = (left + right + 1) // 2
root = TreeNode(nums[mid])
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(nums) - 1)
def sortedArrayToBST3(self, nums: List[int]) -> TreeNode:
def helper(left, right):
if left > right:
return None
# 总是选择中间位置左边的数字作为根节点
mid = (left + right) // 2
root = TreeNode(nums[mid])
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(nums) - 1)
cpp 解法, 执行用时: 12 ms, 内存消耗: 21.3 MB, 提交时间: 2023-10-28 12:49:53
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);
}
TreeNode* helper(vector<int>& 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;
}
};
class Solution2 {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);
}
TreeNode* helper(vector<int>& 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;
}
};
class Solution3 {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);
}
TreeNode* helper(vector<int>& 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;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 42 MB, 提交时间: 2023-10-28 12:49:07
/**
* 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 helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 总是选择中间位置左边的数字作为根节点
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;
}
}
// 中序遍历，总是选择中间位置右边的数字作为根节点
class Solution2 {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 总是选择中间位置右边的数字作为根节点
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;
}
}
// 中序遍历，选择任意一个中间位置数字作为根节点
class Solution3 {
Random rand = new Random();
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 选择任意一个中间位置数字作为根节点
int mid = (left + right + rand.nextInt(2)) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 3.4 MB, 提交时间: 2021-08-16 16:25:29
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedArrayToBST(nums []int) *TreeNode {
return helper(nums, 0, len(nums)-1)
}
func helper(nums []int, left, right int) *TreeNode {
if left > right {
return nil
}
mid := ( left + right ) / 2
root := &TreeNode{
Val:nums[mid],
}
root.Left = helper(nums, left, mid-1)
root.Right = helper(nums, mid+1, right)
return root
}
