包头教育云平台网站建设,wordpress lay,带注册登录的网站模板,wordpress 注册 攻击文章目录 一、题目二、C# 题解 一、题目 给定一个有序整数数组#xff0c;元素各不相同且按升序排列#xff0c;编写一个算法#xff0c;创建一棵高度最小的二叉搜索树。 点击此处跳转题目。
示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是#xff1a;[0,-3,9,-10… 文章目录 一、题目二、C# 题解 一、题目 给定一个有序整数数组元素各不相同且按升序排列编写一个算法创建一棵高度最小的二叉搜索树。 点击此处跳转题目。
示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是[0,-3,9,-10,null,5]它可以表示下面这个高度平衡二叉搜索树 0 / \ -3 9 / / -10 5 二、C# 题解 很基础的题目了。递归中序遍历构建二叉树
/*** Definition for a binary tree node.* public class TreeNode {* public int val;* public TreeNode left;* public TreeNode right;* public TreeNode(int x) { val x; }* }*/
public class Solution {public TreeNode SortedArrayToBST(int[] nums) {return Partition(nums, 0, nums.Length);}public TreeNode Partition(int[] nums, int left, int right) {if (left right) return null;int mid (left right) / 2;TreeNode node new TreeNode(nums[mid]); // 中间元素作为头结点node.left Partition(nums, left, mid); // 左孩子为左方区间处理结果node.right Partition(nums, mid 1, right); // 右孩子为右方区间处理结果return node;}
}时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( log n ) O(\log n) O(logn)。
