leetcode 150道题 计划花两个月时候刷完，今天（第四十八天）完成了3道(90-92)150：
90.（108. 将有序数组转换为二叉搜索树）题目描述：
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
第一版（就每次取数组中间坐标的数作为递归的新树的头结点就行）
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
int len=nums.length;
if(len<=0){
return null;
}
return buildTree(nums,0,nums.length-1);
}
public TreeNode buildTree(int[] nums,int start,int end){
if(start>end){
return null;
}
int headIndex=(end+start)/2;
TreeNode head=new TreeNode(nums[headIndex]);
head.left=buildTree(nums,start,headIndex-1);
head.right=buildTree(nums,headIndex+1,end);
return head;
}
}
91.（148. 排序链表）题目描述：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
输入：head = [4,2,1,3]
输出：[1,2,3,4]
！！！是链表 不是数组
第一版（冒泡链表。。超时了）
class Solution {
public ListNode sortList(ListNode head) {
if(head==null){
return head;
}
ListNode headTemp=head;
while(headTemp!=null){
ListNode min=headTemp;
while(min.next!=null){
if(headTemp.val>min.next.val){
int val=min.next.val;
min.next.val=headTemp.val;
headTemp.val=val;
}
min=min.next;
}
headTemp=headTemp.next;
}
return head;
}
}
第二版（看了解题，感觉是归并排序。。我就照着写了一下。。）
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head,null);
}
public ListNode sortList(ListNode head,ListNode tail) {
if(head==null){
return head;
}
if(head.next==tail){
head.next=null;
return head;
}
// 快慢指针 求链表的中间节点
ListNode slow=head,fast=head;
while(fast!=tail){
slow=slow.next;
fast=fast.next;
if(fast!=tail){
fast=fast.next;
}
}
ListNode mid=slow;
ListNode list1=sortList(head,mid);
ListNode list2=sortList(mid,tail);
ListNode sorted=merge(list1,list2);
return sorted;
}
public ListNode merge(ListNode list1,ListNode list2){
ListNode dumpHead=new ListNode(0);
ListNode temp=dumpHead,temp1=list1,temp2=list2;
while(temp1!=null&&temp2!=null){
if(temp1.val<temp2.val){
temp.next=temp1;
temp1=temp1.next;
}else{
temp.next=temp2;
temp2=temp2.next;
}
temp=temp.next;
}
if(temp!=null){
temp.next=temp1;
}
if(temp2!=null){
temp.next=temp2;
}
return dumpHead.next;
}
}
92.（427. 建立四叉树）题目描述：
给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
你需要返回能表示矩阵 grid 的 四叉树 的根结点。
四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：
val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False。注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
我们可以按以下步骤为二维区域构建四叉树：
如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
使用适当的子网格递归每个子节点。
第一版（题目比较绕。。意思就是从中间分成四份，看他是不是根节点，四个块值都一样，那他就是叶子节点，不一样就是根节点，根节点的val 随便值就行，我自己写的啊第一版，我感觉无敌）
class Solution {
public Node construct(int[][] grid) {
return construct(grid,0,0,grid.length);
}
public Node construct(int[][] grid,int x,int y,int n) {
if(n<1){
return null;
}
Node head=new Node();
head.topLeft=construct(grid,x,y,n/2);
head.topRight=construct(grid,x,y+n/2,n/2);
head.bottomLeft=construct(grid,x+n/2,y,n/2);
head.bottomRight=construct(grid,x+n/2,y+n/2,n/2);
if(head.topLeft==null||head.topRight==null||head.bottomLeft==null||head.bottomRight==null){
head.isLeaf=true;
head.val=grid[x][y]==1;
}else{
// 都是叶子节点了才去合并
if(head.topLeft.isLeaf&&head.topRight.isLeaf&&head.bottomLeft.isLeaf&&head.bottomRight.isLeaf){
if((Boolean.TRUE.equals(head.topLeft.val)&&Boolean.TRUE.equals(head.topRight.val)&&Boolean.TRUE.equals(head.bottomLeft.val)&&Boolean.TRUE.equals(head.bottomRight.val))||
(Boolean.FALSE.equals(head.topLeft.val)&&Boolean.FALSE.equals(head.topRight.val)&&Boolean.FALSE.equals(head.bottomLeft.val)&&Boolean.FALSE.equals(head.bottomRight.val))){
head.isLeaf=true;
head.val=head.topLeft.val;
head.topLeft=null;
head.topRight=null;
head.bottomLeft=null;
head.bottomRight=null;
}
}
}
return head;
}
}
最后一个题把我的自信又提起来了。。。做了一个多小时但是也做出来了！！！
加油早日跳槽！！！
