脸家电话挂经

发个几周前的挂经

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

其实是楼主把问题想复杂了，直接每次扫描求中间的数，递归求解，就满足面试官的要求了。参考LC 给的解法的复杂度分析。

shimmer422 发表于 2020-5-7 12:44
大哥，您这个解法，是把list 当array做了吧。
中间出来一个node.val， node都没定义

您再好好看看 谢谢
是把list 当array做了吧 --- 看都没看懂你在说什么
node最开始的时候就定义了

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

能不能给个Space O(1)的解法看一下？

bigteemo 发表于 2020-5-6 19:37
能不能给个Space O(1)的解法看一下？

1. # Definition for singly-linked list.
   
2. # class ListNode:
   
3. #     def __init__(self, x):
   
4. #         self.val = x
   
5. #         self.next = None
   
6. 
   
7. # Definition for a binary tree node.
   
8. # class TreeNode:
   
9. #     def __init__(self, x):
   
10. #         self.val = x
    
11. #         self.left = None
    
12. #         self.right = None
    
13. 
    
14. class Solution:
    
15. 
    
16.     def findSize(self, head):
    
17.         ptr = head
    
18.         c = 0
    
19.         while ptr:
    
20.             ptr = ptr.next
    
21.             c += 1
    
22.         return c
    
23. 
    
24. 
    
25.     def sortedListToBST(self, head):
    
26.         """
    
27.         :type head: ListNode
    
28.         :rtype: TreeNode
    
29.         """
    
30. 
    
31.         # Get the size of the linked list first
    
32.         size = self.findSize(head)
    
33. 
    
34.         # Recursively form a BST out of linked list from l --> r
    
35.         def convert(l, r):
    
36.             nonlocal head
    
37. 
    
38.             # Invalid case
    
39.             if l > r:
    
40.                 return None
    
41. 
    
42.             mid = (l + r) // 2
    
43. 
    
44.             # First step of simulated inorder traversal. Recursively form
    
45.             # the left half
    
46.             left = convert(l, mid - 1)
    
47. 
    
48.             # Once left half is traversed, process the current node
    
49.             node = TreeNode(head.val)   
    
50.             node.left = left
    
51. 
    
52.             # Maintain the invariance mentioned in the algorithm
    
53.             head = head.next
    
54. 
    
55.             # Recurse on the right hand side and form BST out of them
    
56.             node.right = convert(mid + 1, r)
    
57.             return node
    
58.         return convert(0, size - 1)

复制代码

dfs的stack不算space的话是O(1)，算的话是logn

1. private ListNode node;
   
2. 
   
3. public TreeNode sortedListToBST(ListNode head) {
   
4.         if(head == null){
   
5.                 return null;
   
6.         }
   
7.        
   
8.         int size = 0;
   
9.         ListNode runner = head;
   
10.         node = head;
    
11.        
    
12.         while(runner != null){
    
13.                 runner = runner.next;
    
14.                 size ++;
    
15.         }
    
16.        
    
17.         return inorderHelper(0, size - 1);
    
18. }
    
19. 
    
20. public TreeNode inorderHelper(int start, int end){
    
21.         if(start > end){
    
22.                 return null;
    
23.         }
    
24.        
    
25.         int mid = start + (end - start) / 2;
    
26.         TreeNode left = inorderHelper(start, mid - 1);
    
27.        
    
28.         TreeNode treenode = new TreeNode(node.val);
    
29.         treenode.left = left;
    
30.         node = node.next;
    
31. 
    
32.         TreeNode right = inorderHelper(mid + 1, end);
    
33.         treenode.right = right;
    
34.        
    
35.         return treenode;
    
36. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ningchris 发表于 2020-5-6 21:43
楼主想复杂了

linkedlist 要求找中间都是 快慢指针一起用

我贴的这个是LeetCode的最优解，时间On的

快慢指针的话时间要nlogn的

是把链表变成平衡二叉树那题吗？lc原题要求构造新的TreeNode类型，肯定要O(n)空间啊，除非把链表的next prev直接当left right用

convexopt 发表于 2020-5-6 22:02
是把链表变成平衡二叉树那题吗？lc原题要求构造新的TreeNode类型，肯定要O(n)空间啊，除非把链表的next pre ...

输出占用的空间不算