竞赛讨论区 > 中序遍历 Python OJ 疑似错误
头像
Han3000
发布于 2020-08-07 13:47
+ 关注

中序遍历 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


全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐