不能构建二叉树,直接处理数组。自然想到的方法就是递归了:后序遍历的末尾元素肯定是当前状态的根节点,这样可以发现一个前序遍历节点,并能通过中序遍历划分出左右子树,而左右子树又是一个可以如此解决的子问题,从而我们便很容易用递归写出来。
第一次解这道题的时候,犯了一个逻辑上的错误,将问题复杂化了。(人在紧张的时候容易复杂化,Calm down dude,世界上的公司海了去了,写不出再换一家呗)第二次思考了以后很快就写出来了。

def mysolve(inorder,postorder):

    firstoder = []

    def solve(_inorder, _postorder):
        if not _inorder:
            return

        if len(_inorder) == 1:
            firstoder.append(_inorder[0])
            return

        root = None
        for i in range(len(_postorder)-1,-1,-1):
            if _postorder[i] in _inorder:
                root = _postorder[i]
                break

        if root is None:
            return
        # try:
        firstoder.append(root)
        rid = _inorder.index(root)
        solve(_inorder[:rid], _postorder)
        solve(_inorder[rid+1:], _postorder)
        # except:
        #     print(root,_inorder, _postorder)

    solve(inorder, postorder)

    print(firstoder)

mysolve([9,3,15,20,7], [9,15,7,20,3])
最后修改日期:2020年9月16日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。