e******i
发帖数: 106 | 1 leetcode上单链表转BST上那道题我用JAVA写了，可是测试就是过不了，求大神看看我
的code。
我确实看不出问题在哪儿，不会是getlength那个Method写错了吧
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
// Start typing your Java solution below
// DO NOT write main() function
int length = getListLength(head);
return sortedListToBST(head, 1, length);
}
public TreeNode sortedListToBST(ListNode head, int start, int end){
if(start>end)
return null;
int mid = start + (end-start)/2;
TreeNode leftChild = sortedListToBST(head, start, mid-1);
TreeNode parent = new TreeNode(head.val);
parent.left = leftChild;
head = head.next;
parent.right = sortedListToBST(head, mid+1, end);
return parent;
}
public int getListLength(ListNode head){
ListNode current = head;
int count = 0;
while(current!=null){
count++;
current = current.next;
}
return count;
}
} |
l*****a
发帖数: 14598 | 2 why use head.val as root.val?
【在 e******i 的大作中提到】
: leetcode上单链表转BST上那道题我用JAVA写了，可是测试就是过不了，求大神看看我
: 的code。
: 我确实看不出问题在哪儿，不会是getlength那个Method写错了吧
: public class Solution {
: public TreeNode sortedListToBST(ListNode head) {
: // Start typing your Java solution below
: // DO NOT write main() function
: int length = getListLength(head);
: return sortedListToBST(head, 1, length);
: }
|
b*****n
发帖数: 482 | 3 parent应该是中间的node，head~mid-1是左子树，mid+1到tail是右子树。你的code有
两个
比较大的问题。
1. parent 选了head，这样对于有序链表来说，即使生成了树也是degenerated tree,
还是一个链表。parent最好是选mid node，可以生成平衡二叉树。
2. recursived左子树的时候，pass了head，造成head node的left child指向了自己。
你如果pass了有序数组转BST的那题，可以把中间二叉树的生成过程打出来，就会比较
清楚整个思路了。
【在 e******i 的大作中提到】
: leetcode上单链表转BST上那道题我用JAVA写了，可是测试就是过不了，求大神看看我
: 的code。
: 我确实看不出问题在哪儿，不会是getlength那个Method写错了吧
: public class Solution {
: public TreeNode sortedListToBST(ListNode head) {
: // Start typing your Java solution below
: // DO NOT write main() function
: int length = getListLength(head);
: return sortedListToBST(head, 1, length);
: }
|
e******i
发帖数: 106 | 4
,
谢谢指导，我来顺着你的思路看看，我是把leetcode上那篇blog里的copy过来，结果不
行。一时半会儿还真没有看出问题
【在 b*****n 的大作中提到】
: parent应该是中间的node，head~mid-1是左子树，mid+1到tail是右子树。你的code有
: 两个
: 比较大的问题。
: 1. parent 选了head，这样对于有序链表来说，即使生成了树也是degenerated tree,
: 还是一个链表。parent最好是选mid node，可以生成平衡二叉树。
: 2. recursived左子树的时候，pass了head，造成head node的left child指向了自己。
: 你如果pass了有序数组转BST的那题，可以把中间二叉树的生成过程打出来，就会比较
: 清楚整个思路了。
|
p*****2
发帖数: 21240 | 5
最好不要copy
【在 e******i 的大作中提到】
:
: ,
: 谢谢指导，我来顺着你的思路看看，我是把leetcode上那篇blog里的copy过来，结果不
: 行。一时半会儿还真没有看出问题
|
e******i
发帖数: 106 | 6
是！我正在拜读您的博客。。。。
【在 p*****2 的大作中提到】
:
: 最好不要copy
|
l*****a
发帖数: 14598 | 7 最好也不要copy
【在 e******i 的大作中提到】
:
: 是！我正在拜读您的博客。。。。
|
e******i
发帖数: 106 | 8 哼！╭(╯^╰)╮
【在 l*****a 的大作中提到】
: 最好也不要copy
|
b*****n
发帖数: 482 | 9 呵呵，不客气，一起研究。理解解题思路很重要 :)
【在 e******i 的大作中提到】
: 哼！╭(╯^╰)╮
|
z*****e
发帖数: 231 | 10 if you use C++, the head should be passed by the reference, so the head
value will be updated in the recursive call.
In java, how to pass by reference? |
w***o
发帖数: 109 | 11 java 不能从被调用的函数里去改变调用函数的值。一定用定义一个新class去封装
ListNode。一个workaround就是用只有一个元素的数组。
比如：
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
int n= 0;
ListNode c = head;
while(c != null) {
n++;
c=c.next;
}
ListNode[] list = new ListNode[1];
list[0] = head;
return convert(list, 0, n-1);
}
TreeNode convert(ListNode[] list, int l, int r) {
if(l > r)
return null;
int m = l + (r-l)/2;
TreeNode left = convert(list, l, m-1);
TreeNode ret = new TreeNode(list[0].val);
ret.left = left;
list[0] = list[0].next;
TreeNode right = convert(list, m+1, r);
ret.right = right;
return ret;
}
} |
n****r
发帖数: 120 | 12 LeetCode上对Java的建议是可以是用一个全局变量来保存head！这个是可行的。另外一
个方法就是把head包在一个数组里，传入该数组 |
