G暑期实习店面

timeline见：https://www.1point3acres.com/bbs/thread-560589-1-1.html店面两轮背靠背，一轮一小时，运气很好，没问难题，听起来都是白人大哥

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

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

求加米，顺便求team match经验！

感谢楼主分享,请问第一轮follow-up O(1) space 有没有额外条件， 没想到该怎么做

记忆中的微光 发表于 2019/10/18 06:05:29
感谢楼主分享,请问第一轮follow-up O(1) space 有没有额外条件， 没想到该怎么做

你可以查查Morris traversal，差不多就是那个思路，traverse下去的时候要把left改成parent

this is a hard one....

1. class Node():
   
2.     def __init__(self, val):
   
3.         self.val = val
   
4.         self.left = None
   
5.         self.right = None
   
6. 
   
7. 
   
8. 
   
9. 
   
10. 
    
11. 
    
12. class Solution():
    
13.     def dfs(self, root):
    
14.         if root == None:
    
15.             return 0
    
16.         if root.left == root.right == None:
    
17.             return root.val
    
18.         return self.dfs(root.left) + self.dfs(root.right)
    
19. 
    
20.     def iter(self, root):
    
21.         stack = []
    
22.         cur = root
    
23.         sum_ = 0
    
24.         while True:
    
25.             while cur:
    
26.                 stack.append(cur)
    
27.                 cur = cur.left
    
28.             if len(stack) > 0:
    
29.                 temp = stack.pop()
    
30.                 cur =temp.right
    
31.                 if temp.left == temp.right == None:
    
32.                     sum_ += temp.val
    
33.             else:
    
34.                 break
    
35.         return sum_
    
36. 
    
37. 
    
38.     def iter1(self, root):
    
39.         stack = []
    
40.         cur = root
    
41.         sum_ = 0
    
42.         while stack or cur:
    
43.             while cur:
    
44.                 stack.append(cur)
    
45.                 cur = cur.left
    
46. 
    
47.             temp = stack.pop()
    
48.             cur =temp.right
    
49.             if temp.left == temp.right == None:
    
50.                 sum_ += temp.val
    
51. 
    
52.         return sum_
    
53. 
    
54.     def time_complexity_1(self, root):
    
55. 
    
56.         sum_ = 0
    
57.         cur = root
    
58. 
    
59.         while cur:
    
60.             print("cur", cur.val)
    
61.             # find the rightest node r
    
62.             r = cur.left
    
63.             if r == None: # if cur.left == None, go cur.right
    
64.                 if cur.right == None:
    
65.                     sum_ += cur.val
    
66.                 cur = cur.right
    
67.                 print('if cur.left == None, go cur.right,,, cur=', cur.val if cur else None)
    
68.                 ##################
    
69.                 continue
    
70.             while r.right:
    
71. 
    
72.                 r = r.right
    
73.                 if r == cur:
    
74.                     print('find a loop', cur.val)
    
75.                     # cur = cur.right
    
76.                     '''
    
77.                     need to break two loop
    
78.                     '''
    
79.                     break
    
80.             if r == cur:
    
81.                 cur = cur.right
    
82.                 continue
    
83.             print('find the rightest node r', r.val)
    
84. 
    
85.             #check if it is a leaf
    
86.             if r.left == r.right == None:
    
87.                 sum_ += r.val
    
88.             # r.right = cur
    
89.             r.right = cur
    
90.             print('r.right', r.right.val)
    
91.             print("")
    
92.             cur = cur.left
    
93.         return sum_
    
94. 
    
95. 
    
96. 
    
97. 
    
98. 
    
99. 
    
100. 
     
101. root = Node(10)
     
102. 
     
103. root.left = Node(5)
     
104. root.right = Node(30)
     
105. root.right.right = Node(40)
     
106. 
     
107. root.left.left = Node(-2)
     
108. root.left.right = Node(6)
     
109. root.left.right.right = Node(8)
     
110. 
     
111. root.left.left.right = Node(2)
     
112. root.left.left.right.left = Node(-1)
     
113. 
     
114. a = Solution()
     
115. print(a.dfs(root))
     
116. print(a.iter1(root))
     
117. print(a.time_complexity_1(root))

复制代码

楼主已经过了hc吗