Preorder 및 Postorder Traversal에서 이진 트리 구성

2256 단어 leetcodetheabbiedsa
preorderpostorder 두 개의 정수 배열이 주어지면 preorder는 고유한 값의 이진 트리의 전위 순회이고 postorder는 동일한 트리의 후위 순회입니다. 이진 트리를 재구성하고 반환합니다.

답이 여러 개인 경우 그 중 하나를 반환할 수 있습니다.

예 1:



입력: 사전 주문 = [1,2,4,5,3,6,7], 사후 주문 = [4,5,2,6,7,3,1]
출력: [1,2,3,4,5,6,7]

예 2:

입력: 사전 주문 = [1], 사후 주문 = [1]
출력: [1]

제약:
  • 1 <= preorder.length <= 30
  • 1 <= preorder[i] <= preorder.length
  • preorder의 모든 값은 고유합니다.
  • postorder.length == preorder.length
  • 1 <= postorder[i] <= postorder.length
  • postorder의 모든 값은 고유합니다.
  • preorderpostorder가 동일한 이진 트리의 선위 순회 및 후위 순회임을 보장합니다.

  • 해결책:

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def makeTree(self, preorder, pri, prj, prepos, postorder, poi, poj, postpos):
            if pri >= prj:
                return None
            root = TreeNode(val = preorder[pri])
            if pri + 1 == prj:
                return root
            leftval = preorder[pri + 1]
            rightval = postorder[poj - 2]
            root.left = self.makeTree(preorder, pri + 1, prepos[rightval], prepos, postorder, poi, postpos[leftval] + 1, postpos)
            root.right = self.makeTree(preorder, prepos[rightval], prj, prepos, postorder, postpos[leftval] + 1, poj - 1, postpos)
            return root
    
        def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
            n = len(preorder)
            prepos = {}
            postpos = {}
            for i, preval in enumerate(preorder):
                prepos[preval] = i
            for i, postval in enumerate(postorder):
                postpos[postval] = i
            return self.makeTree(preorder, 0, n, prepos, postorder, 0, n, postpos)
    

    좋은 웹페이지 즐겨찾기