My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null)
return null;
int total = 1;
ListNode temp = head;
while (temp.next != null) {
temp = temp.next;
total++;
}
return getBST(1, total, head, temp);
}
private TreeNode getBST(int begin, int end, ListNode beginNode, ListNode endNode) {
if (begin > end)
return null;
else if (begin == end)
return new TreeNode(beginNode.val);
int mid = (begin + end) / 2;
ListNode dummy = new ListNode(Integer.MIN_VALUE);
dummy.next = beginNode;
ListNode temp = beginNode;
ListNode pre = dummy;
ListNode post = temp.next;
for (int i = begin; i <= end; i++) {
if (i == mid)
break;
else {
pre = pre.next;
temp = pre.next;
post = temp.next;
}
}
TreeNode root = new TreeNode(temp.val);
if (pre == dummy) {
root.left = null;
root.right = getBST(mid + 1, end, post, endNode);
}
else {
root.left = getBST(begin, mid - 1, beginNode, pre);
root.right = getBST(mid + 1, end, post, endNode);
}
return root;
}
}
My test result:
这道题目不难，感觉就是用二叉搜索法将链表改造成balanced BST
1 -> 2 -> 3 -> 4 -> 5
begin = 1; end = 5; mid = 3
3 will be the root and
the left should be getBST(...., begin, mid - 1)
the right should be getBST(...., mid + 1, end)
SO:
1 -> 2
begin = 1, end = 2; mid = 1
1 will be the root and
the left should be null
the right should be getBST(...., mid + 1, end)
SO:
2
begin = 2; end = 2; mid = 2
2 will be the root and
we don't need to take care of its left and right tree which means they are null.
SO:
4 -> 5
begin = 4; end = 5; mid = 4
...
基本是相同的流程，然后就可以写出一个DFS出来。
下面复习下，什么是 balanced bst
bst 的问题就在于树的结构根据输入结果的顺序而变化，不可人为控制，导致经常性复杂度很大。
于是设计出了balanced bst ，可以进行自我调节。
比如有， AVL, red-black tree 等等。
他们的统一要求是，
http://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html
之前做的一道题目需要判断一棵给定的树是不是balanced。马上在复习下。
http://www.jianshu.com/p/b17a7c404ff6
**
然后这里介绍一个技巧，是我之前完全不知道的。
用快慢指针来找一个链表的中点。
慢指针走一步，快指针走两步，同时每次循环都得判断下，
fast.next != null && fast.next.next != null
同时还有个细节。
如果是奇数个结点，则此时将中间值压入栈中了，事实上没有数字和他对应，所以需要手动弹出。
这是链表的一个小技巧。
还有个小技巧就是，设置 dummy head。 可以简单地通过许多corner case.
**
看了自己的代码，实在是不忍心看。太丑了。而且没有用快慢指针。
于是用快慢指针实现之。
public TreeNode sortedListToBST(ListNode head) {
if (head == null)
return null;
ListNode tail = head;
while (tail.next != null)
tail = tail.next;
return form(head, tail);
}
public TreeNode form(ListNode head, ListNode tail) {
if (head == tail)
return new TreeNode(head.val);
ListNode pre = null;
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
TreeNode root = new TreeNode(slow.val);
if (pre != null) {
pre.next = null;
root.left = form(head, pre);
}
if (slow.next != null)
root.right = form(slow.next, tail);
return root;
}
但是一开始写的时候我是错的，一直爆栈。
后来发现，
要加上 pre.next = null; 这么一句来切断其与后面结点的联系。否则，快指针可以一直往后走，就会报错！
千万要注意这个错误。这在 sort list 里面，我也犯过同样的错误！
还有个bug今天我也是通过debug才找出来的。
当写for循环时。
for (int i = 0; i < N; i++) {...}
一定要注意，N会不会在循环过程中发生改变。如果会改变，而你忽略了，就会产生你无法发现的bug。因为N不会变已经刻入你的大脑了，你不会往这个方向去找bug
一定要当心！
把链表分成两个子链表处理最后汇总时，记得之前要切断左子链表与中间结点的连接，在许多情况下！
for的N会不会变，要去想一下！
**
总结： sorted ascending linked list -> balanced bst
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
return helper(head);
}
private TreeNode helper(ListNode head) {
if (head == null)
return null;
else if (head.next == null)
return new TreeNode(head.val);
ListNode slow = head;
ListNode fast = head;
ListNode pre = head;
/** find the middle node of this linked list */
while (fast.next != null && fast.next.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next;
fast = fast.next;
}
/** cut the connection */
ListNode right = slow.next;
slow.next = null;
pre.next = null;
TreeNode root = new TreeNode(slow.val);
if (head != slow)
root.left = helper(head);
if (right != slow)
root.right = helper(right);
return root;
}
}
自己写的。就是走到中间，切开。中间结点和他前面一个结点也要切开。然后中间结点作 root。然后继续递归。
写了这么多道链表题目，眼睛发花了。想不动了。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
return helper(head);
}
private TreeNode helper(ListNode head) {
if (head == null) {
return null;
}
else if (head.next == null) {
return new TreeNode(head.val);
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode slow = head;
ListNode fast = head;
ListNode pre = dummy;
while (fast.next != null && fast.next.next != null) {
pre = pre.next;
slow = slow.next;
fast = fast.next.next;
}
ListNode left = (head == slow ? null : head);
ListNode right = slow.next;
slow.next = null;
pre.next = null;
TreeNode root = new TreeNode(slow.val);
root.left = helper(left);
root.right = helper(right);
return root;
}
}
这道题目不难，但是有挺多注意点。
首先，找到中点后，第一个思路就是断开他与后面的联系。
但是忘了一点，也得断开他与左边子链表的联系。所以得有个pre指针。
其次，左边以head开头，他很可能等于 这个中间节点，得考虑到这种情况。
然后，就差不多了。
Anyway, Good luck, Richardo! -- 08/16/2016
