Hexo

思路

[9,3,15,20,7]
[9,15,7,20,3]

• 1.用L表示左子树，P代表根，R代表右子树
• 2.中序序列可表示为 LPR, 后序序列可表示为 LRP
• 3.后序序列的最后一个元素是二叉树的根，如3
• 4.根据根的值可以把中序序列分为两部分[9]和[3,15,20, 7]
• 5.中序两部分元素个数分别为1，4
• 6.根据中序元素个数把后续分为两部分[9]和[15, 7, 20, 3]
• 7.用中序和后序对应的部分分别创建树的左子树和右子树

代码

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        
        def helper(il, ir, pl, pr):
            if (il == ir or pl == pr):
                return None
        
            root = TreeNode(postorder[pr-1])
            inRootPos = inorder.index(root.val, il, ir)
            rightSize = ir - inRootPos
            
            root.right = helper(inRootPos + 1, ir, pr - rightSize, pr - 1)
            root.left = helper(il, inRootPos, pl, pr - rightSize)
            return root
            
        return helper(0, len(inorder), 0, len(postorder))

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦