Convert Sorted List to Binary Search Tree

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) { val = x; }
   
7. * }
   
8. */
   
9. /**
   
10. * Definition for a binary tree node.
    
11. * public class TreeNode {
    
12. *     int val;
    
13. *     TreeNode left;
    
14. *     TreeNode right;
    
15. *     TreeNode(int x) { val = x; }
    
16. * }
    
17. */
    
18. public class Solution {
    
19.     static ListNode h;
    
20.     public TreeNode sortedListToBST(ListNode head) {
    
21.         if(head==null) return null;
    
22.         int len=0;
    
23.         h=head;
    
24.         ListNode tmp=head;
    
25.         while(tmp!=null) {
    
26.             len++;
    
27.             tmp=tmp.next;
    
28.         }
    
29.         return myBuild(0,len-1);
    
30.     }
    
31.     public TreeNode myBuild(int low,int high) {
    
32.         if(low>high) return null;
    
33.         int mid=(low+high)/2;
    
34.         TreeNode left=myBuild(low,mid-1);
    
35.         TreeNode root=new TreeNode(h.val);   //递归看不太懂。。。
    
36.         root.left=left;
    
37.         h=h.next;
    
38.         TreeNode right=myBuild(mid+1,high);
    
39.         root.right=right;
    
40.         return root;
    
41.     }
    
42. }

复制代码

递归看不懂啊，说的是从下往上生成树，可是是怎么生成的。。。可否解释下
TreeNode root=new TreeNode(h.val);   //递归看不太懂。。。
        root.left=left;
        h=h.next;
        TreeNode right=myBuild(mid+1,high);
        root.right=right;   这5行程序是怎么跑的。。。。谢谢了！

这个递归的唯一难点在于：如何能够在每次递归调用中，用O(1)时间内获得链表中部的节点？这也是此题和Convert Array to BST的最大不同之处。

在一般情况下，这点本来是做不到的，但是在这里我们可以通过递归“累积”的方式来实现。设想，我们维护一个全局变量h，最初指向左半链表的头。我们每处理一个左链表的节点，h就向后移动一位。这样，当我们处理完左半链表时，h正好处于左半链表尾的下一个元素，这个元素恰好是整个树的root，所以我们才使用h.val来初始化root。之所以递归必须是中序，是因为h只有在左半链表都处理完毕后才能获得。

每次递归的参数是low和high，返回的是生成的BST的根节点，根节点就是mid。然后递归获得[low, mid-1]的根节点，即为当前递归栈的根节点的左子树根节点；递归获得[mid+1, high]的根节点，即为当前递归栈的根节点的右子树根节点。

不要去想递归是怎么做的，要想递归是做的什么。

希望对你有帮助。

yhfyhf 发表于 2015-6-27 16:57
每次递归的参数是low和high，返回的是生成的BST的根节点，根节点就是mid。然后递归获得[low, mid-1]的根节 ...

但是为什么根节点是mid呢
        TreeNode root=new TreeNode(h.val);    h.val应该是链表头结点啊

zh355245849 发表于 2015-6-27 17:08
但是为什么根节点是mid呢
        TreeNode root=new TreeNode(h.val);    h.val应该是链表头结点啊

sorry，看错题目了，看成array to BST那题了。这题其实跟树的中序遍历差不多，额，感觉挺难解释的...

yhfyhf 发表于 2015-6-27 17:13
sorry，看错题目了，看成array to BST那题了。这题其实跟树的中序遍历差不多，额，感觉挺难解释的...

zh355245849 发表于 2015-6-27 17:16

首先通过递归走到BST的最左下方，然后链表通过next移动，自底向上构建根节点，最后再构建右子树，就像中序遍历一样... 不知道这样解释你能否理解....

yhfyhf 发表于 2015-6-27 17:23
首先通过递归走到BST的最左下方，然后链表通过next移动，自底向上构建根节点，最后再构建右子树，就像中 ...

我理解了。。。但是还是不明白递归为什么这样写以及写在哪一行合适。。。现在好像只能看明白return 递归的那种了。。。。

zh355245849 发表于 2015-6-27 17:32
我理解了。。。但是还是不明白递归为什么这样写以及写在哪一行合适。。。现在好像只能看明白return 递归 ...

因为它是一个中序遍历，所以一定要按那个顺序写。