中序遍历 Python OJ 疑似错误
中序遍历的Python OJ, 疑似错误。
以下三组代码，全部case通过率为91.67%
class Solution: def solve(self, n, pre, post): self.preIndex, self.posIndex = 0, 0 res = [] def work(): root = pre[self.preIndex] self.preIndex += 1 if (root != post[self.posIndex]): work() res.append(root) if (root != post[self.posIndex]): work() self.posIndex += 1 work() return res
class Solution:
def solve(self, n, pre, post):
d = {a: i for i, a in enumerate(post)}
res = []
def work(i, j, a, b):
# print i, j, a, b
if i >= j: return
if i + 1 == j:
res.append(pre[i])
return
left = d[pre[i + 1]] - a + 1
work(i + 1, i + 1 + left, a, a + left)
res.append(pre[i])
work(i + 1 + left, j, a + left, b - 1)
work(0, n, 0, n)
return res 改编自 @JOHNKRAM C++ 代码class Solution:
def solve(self, n, pre, post):
c = {a: i + 1 for i, a in enumerate(post)}
a = [0] + pre
b = [0] + post
ans = []
def work(l1, r1, l2, r2):
if(l1 > r1): return
if(l1 == r1):
ans.append(a[l1])
return
mid = c[a[l1 + 1]]
work(l1 + 1, l1 + 1 + mid - l2, l2, mid)
ans.append(a[l1])
work(l1 + 2 + mid - l2, r1, mid + 1, r2 - 1)
work(1, n, 1, n)
return ans 
投递七牛云等公司10个岗位
