leetCode ✏ Leetcode基础刷题之(108. Convert Sorted Array to Binary Search Tree)
2019-02-28 吴亲库里 库里的深夜食堂
✏ 题目描述
给定一个数组,转换为高度平衡的二叉查找树
✏ 题目分析
首先我们先来了解一下什么是二叉查找树,他的规则又是什么?
二叉查找树,又可以叫二叉搜索树,二叉排序树,或者是一颗空树,或者具有下列性质:若它的左子树不空,则左子树上所有节点的值均小于他的根节点的值,若他的右子树不为空,则他它右字树上所有节点的值均大于他的根节点的值.他的左右子树均为二叉查找树.
这里还需要注意的单词是 height balanced BST 也就是高度平衡的二叉查找树,具体转换成什么样的?
只要最终我们树满足上述的条件,他就是一颗二叉查找树.实例中给出的[-10,-3,0,5,9],最终转换为[0,-3,9,-10,null,5]
这里我先来按照平常我们来解这种问题(非计算机解决),找出数组中最中间的位置最为根节点,为了满足高度差的绝对值大于等于1,所以我们取中间点作为根,这里数组中获取的是0,他就是树的根节点,把数组左边的数到根节点为止作为他的左子树,根节点自后的树作为他的右子树,所以这里的左字树就是[-10,-3],右子树就是[0,5,9].
然后我们重复以上的操作,将左右子树右分别分割成两个部分,左字树的根节点就是-3,右子树的根节点是5,这里特别要注意的是,左子树当前就两个数,取中间点作为根,为什么是-3,而不是-10(自己动手做一下),一直这样取值下去直到去完整个数组的值(好吧,可能你已经知道了,这道题我们还是可以用递归去实现它),这个时候,他就是一棵二叉查找树了.
我们获取最中间的节点下标就是个数除以2,在php中也就是 count(x) /2
✏最终实现代码
/**
* @param Integer[] $nums
* @return TreeNode
*/
function sortedArrayToBST($nums) {
if(!$nums){
return;
}
$mid=floor(count($nums) / 2);
$root=new TreeNode($nums[$mid]);
$root->left=$this->sortedArrayToBST(array_slice($nums,0,$mid));
$root->right=$this->sortedArrayToBST(array_slice($nums,$mid+1));
return $root;
}
PHP函数之array_slice
array_slice ( array $array , int $offset [, int $length = NULL [, bool $preserve_keys = FALSE ]] ) : array
开始今天的数据库题目(176. Second Highest Salary)
💾题目描述
找出工资表中第二高的工资
💾题目分析
按降序对工资进行排序，然后利用 limit 1 offset 1来获取第二高薪，如果不存在的话查询的时候加了IFNULL,这里要注意的是limit 1 offset 1的用法，从第一行（0开始）开始的一条数据,第一个数子limit 1 表示的是检索多少行数据，第二个 offset 1 表示从哪开始（0是起始位置，我们这里是1所以就是第二）
💾最终实现sql
SELECT IFNULL((SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT 1,1),NULL) AS SecondHighestSalary
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)