LeetCode_105_이전 순서와 중간 순서 반복 순서 구조 두 갈래 나무_hn
제목 설명
한 그루의 나무의 전차적 역류와 중차적 역류에 따라 두 갈래 나무를 구성한다.
주의: 트리에 중복된 요소가 없다고 가정할 수 있습니다.
예를 들어 preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
다음 두 갈래 트리로 돌아갑니다. 3
/ \
9 20
/ \
15 7
해답 방법
방법1: 귀속
생각
먼저 앞의 차례와 중간의 차례가 무엇인지 알아보자.
앞의 순서 반복: 앞의 순서는 아버지 노드->왼쪽 하위 노드->오른쪽 하위 노드 뒤의 순서: 앞의 순서는 왼쪽 하위 노드->아버지 노드->오른쪽 하위 노드입니다. 우리는 앞의 순서는 첫 번째 원소가 루트 노드이고 뒷의 순서는 이 루트 노드가 있는 위치의 왼쪽이 왼쪽 나무이고 오른쪽이 오른쪽 하위 나무라는 것을 발견할 수 있습니다.
예제:
앞의 순서는 preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
preorder의 첫 번째 원소 3은 나무 전체의 뿌리 노드입니다.order 중 3의 왼쪽[9]은 나무의 왼쪽 자목이고 오른쪽[15, 20, 7]은 나무의 오른쪽 자목을 구성한다.
그래서 두 갈래 나무를 구축하는 문제는 본질적으로 다음과 같다.
1. 각 하위 트리의 루트 노드를 찾아서 루트 2, 이 루트 노드를 구축하는 왼쪽 하위 트리 3, 이 루트 노드를 구축하는 오른쪽 하위 트리
코드
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) == 0:
return None
#
root = TreeNode(preorder[0])
# ，
i = inorder.index(preorder[0])
#
root.left = self.buildTree(preorder[1:i+1], inorder[:i])
#
root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
return root
시간 복잡도
공간 복잡도
결과 제출
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
3
/ \
9 20
/ \
15 7
방법1: 귀속
생각
먼저 앞의 차례와 중간의 차례가 무엇인지 알아보자.
앞의 순서 반복: 앞의 순서는 아버지 노드->왼쪽 하위 노드->오른쪽 하위 노드 뒤의 순서: 앞의 순서는 왼쪽 하위 노드->아버지 노드->오른쪽 하위 노드입니다. 우리는 앞의 순서는 첫 번째 원소가 루트 노드이고 뒷의 순서는 이 루트 노드가 있는 위치의 왼쪽이 왼쪽 나무이고 오른쪽이 오른쪽 하위 나무라는 것을 발견할 수 있습니다.
예제:
앞의 순서는 preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
preorder의 첫 번째 원소 3은 나무 전체의 뿌리 노드입니다.order 중 3의 왼쪽[9]은 나무의 왼쪽 자목이고 오른쪽[15, 20, 7]은 나무의 오른쪽 자목을 구성한다.
그래서 두 갈래 나무를 구축하는 문제는 본질적으로 다음과 같다.
1. 각 하위 트리의 루트 노드를 찾아서 루트 2, 이 루트 노드를 구축하는 왼쪽 하위 트리 3, 이 루트 노드를 구축하는 오른쪽 하위 트리
코드
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) == 0:
return None
#
root = TreeNode(preorder[0])
# ，
i = inorder.index(preorder[0])
#
root.left = self.buildTree(preorder[1:i+1], inorder[:i])
#
root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
return root
시간 복잡도
공간 복잡도
결과 제출
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
