第三题【先序+后序,求中序】Python实现方法,准确率90%以上,不清楚哪个边界没考虑完全

中序序列

https://ac.nowcoder.com/acm/contest/6779/C

# 第三题【先序 后序,求中序】Python实现方法,准确率90%以上,不清楚哪个边界没考虑
#
# 返回所求中序序列
# @param n int整型 二叉树节点数量
# @param pre int整型一维数组 前序序列
# @param suf int整型一维数组 后序序列
# @return int整型一维数组
#
class TreeNode:
    # 树的初始化定义,包括值、左节点、右节点
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right

class Solution:
    def Calculation(self, n, pre, suf):
        # 递归过程,逐一分析出节点的值、左子树、右子树
        if len(pre) == 0 and len(suf) == 0:
            return None
        if len(pre) == 1 and len(suf) == 1:
            result = TreeNode(pre[0], None, None)
            return result
        index = suf.index(pre[1])
        left = self.Calculation(index + 1, pre[1:index + 2], suf[:index + 1])
        right = self.Calculation(n - index - 2, pre[index + 2:], suf[index + 1:-1])
        root = TreeNode(pre[0], left, right)
        return root

    def inorderTraversal(self, root):
        # 将Calculation返回的树结构,按照中序排列的列表打印出来
        if root == None:
            return []
        if root.left == None and root.right == None:
            return [root.val]
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)
        return left + [root.val] + right

    def solve(self, n, pre, suf):
        if len(pre) != n or len(suf) != n:
            return False
        root = self.Calculation(n, pre, suf)
        return self.inorderTraversal(root)


 
全部评论
感谢大佬的指导,找到原因了,python递归是有限的,需在函数前将递归深度进行调整。 见 https://blog.csdn.net/huludan/article/details/51495697 import sys sys.setrecursionlimit(1000000) #调整递归深度
点赞
送花
回复 分享
发布于 2020-08-12 13:00

相关推荐

黎明azzz:刘女士吓坏了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务