[leetcode] 105. Construct Binary Tree from Preorder and Inorder Traversal

問題の説明

アクセス1-Recursion

コード1

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        left = right = None 
        num = len(preorder)
        if num == 0: return left
        
        root = TreeNode(preorder[0])
        if num == 1: return root
        elif num == 2:
            if preorder == inorder:
                right = TreeNode(preorder[1])
            else:
                left = TreeNode(preorder[1])
        else:
            rootIdx = inorder.index(root.val)
            left = self.buildTree(preorder[1:rootIdx + 1], inorder[:rootIdx])
            right = self.buildTree(preorder[rootIdx+1:], inorder[rootIdx+1:])
        root.left = left
        root.right = right 
        return root

アクセス2-アプリケーションの復元

コード2

class Solution:
    def buildTree(self, preorder, inorder):
        def build(stop):
            if inorder and inorder[-1] != stop:
                root = TreeNode(preorder.pop())
                root.left = build(root.val)
                inorder.pop()
                root.right = build(stop)
                return root
        preorder.reverse()
        inorder.reverse()
        return build(None)