一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 559|回复: 8
收起左侧

[Leetcode] Convert Sorted List to Binary Search Tree

[复制链接] |试试Instant~ |关注本帖
zh355245849 发表于 2015-6-27 16:45:19 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
  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行程序是怎么跑的。。。。谢谢了!
yhfyhf 发表于 2015-6-27 16:57:28 | 显示全部楼层
本帖最后由 yhfyhf 于 2015-6-27 17:06 编辑

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

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

希望对你有帮助。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| zh355245849 发表于 2015-6-27 17:08:01 | 显示全部楼层
yhfyhf 发表于 2015-6-27 16:57
每次递归的参数是low和high,返回的是生成的BST的根节点,根节点就是mid。然后递归获得[low, mid-1]的根节 ...

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

使用道具 举报

yhfyhf 发表于 2015-6-27 17:13:32 | 显示全部楼层
zh355245849 发表于 2015-6-27 17:08
但是为什么根节点是mid呢
        TreeNode root=new TreeNode(h.val);    h.val应该是链表头结点啊

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

使用道具 举报

 楼主| zh355245849 发表于 2015-6-27 17:16:19 | 显示全部楼层
yhfyhf 发表于 2015-6-27 17:13
sorry,看错题目了,看成array to BST那题了。这题其实跟树的中序遍历差不多,额,感觉挺难解释的...

回复 支持 反对

使用道具 举报

yhfyhf 发表于 2015-6-27 17:23:47 | 显示全部楼层

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| zh355245849 发表于 2015-6-27 17:32:50 | 显示全部楼层
yhfyhf 发表于 2015-6-27 17:23
首先通过递归走到BST的最左下方,然后链表通过next移动,自底向上构建根节点,最后再构建右子树,就像中 ...

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

使用道具 举报

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

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-27 19:26:08 | 显示全部楼层
这个递归的唯一难点在于:如何能够在每次递归调用中,用O(1)时间内获得链表中部的节点?这也是此题和Convert Array to BST的最大不同之处。

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 00:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表