[Leetcode] 0105. 전위순회와 중위순회를 통한 이진트리 구성

/ 리트코드, 기술 기사 / 에 의해

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

두 개의 정수 배열이 주어지면 사전 주문 그리고 순서대로 어디 사전 주문 이진 트리의 사전 순회이며 순서대로 같은 트리의 중위 순회이며, 구성하고 반환합니다. 이진 트리.

 

예시 1:

입력: 사전순서 = [3,9,20,15,7], 내순서 = [9,3,15,20,7]
산출: [3,9,20,널,널,15,7]

예 2:

입력: 사전 주문 = [-1], 내차 = [-1]
산출: [-1]

 

제약:

  • 1 <= 사전 주문 길이 <= 3000
  • inorder.length == 사전 주문.길이
  • -3000 <= 사전 주문[i], 내순서[i] <= 3000
  • 사전 주문 그리고 순서대로 ~로 구성되다 고유한 가치.
  • 각 값 순서대로 또한 나타납니다 사전 주문.
  • 사전 주문 ~이다 보장 트리의 전위 순회가 됩니다.
  • 순서대로 ~이다 보장 트리의 중위 순회를 의미합니다.
 

파이썬

				
					# 시간 복잡도: O(n) # 공간 복잡도: O(n) import List, Optional 클래스 입력 솔루션: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: def dfs(left: int, right: int): nonlocal preorderIndex if left > right: return None rootValue = preorder[preorderIndex] root = TreeNode(rootValue) preorderIndex += 1 root.left = dfs(left, inorderMap[rootValue] - 1) root.right = dfs(inorderMap[rootValue] + 1, right) return root preorderIndex = 0 inorderMap = {} for i, value in enumerate(inorder): inorderMap[value] = i return dfs(0, len(inorder) - 1) preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7] print(Solution().buildTree(전위순, 중위순))

관련 기사

ko_KR한국어
zh_TW繁體中文 en_USEnglish zh_CN简体中文 ja日本語 es_ESEspañol ko_KR한국어