114. Flatten Binary Tree to Linked List 두 갈래 트리를 체인 테이블로 확장합니다.
예를 들어, 지정된 두 갈래 트리
1
/ \
2 5
/ \ \
3 4 6
다음으로 확장:
1
\
2
\
3
\
4
\
5
\
6
앞차례 를 두루 다니다
두 갈래 트리를 단일 체인 테이블로 펼친 후, 단일 체인 테이블의 노드 순서는 두 갈래 트리의 앞 순서로 각 노드에 접근하는 순서입니다.따라서 두 갈래 트리를 앞뒤로 훑어보고 각 노드가 방문한 순서를 얻을 수 있다.두 갈래 나무를 체인 테이블로 펼치면 두 갈래 나무의 구조가 파괴되기 때문에 앞의 순서가 끝난 후에 각 노드의 좌우 노드 정보를 업데이트하고 두 갈래 나무를 단일 체인 테이블로 전개합니다.
Code
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def preOrderTraversal(root: TreeNode):
if root:
preOrderList.append(root)
preOrderTraversal(root.left)
preOrderTraversal(root.right)
preOrderList = []
preOrderTraversal(root)
size = len(preOrderList)
for i in range(1, size):
prev, curr = preOrderList[i - 1], preOrderList[i]
prev.left = None
prev.right = curr
복잡도 분석
시간 복잡도: O(n), 그중 n은 두 갈래 나무의 노드 수입니다.앞뒤로 흐르는 시간의 복잡도는 O(n)이고, 앞뒤로 흐르는 시간의 복잡도는 각 노드에 대해 좌우 하위 노드의 정보를 업데이트해야 하며, 시간의 복잡도도 O(n)이다.
공간 복잡도: O(n), 그중 n은 두 갈래 나무의 노드 수이다.공간의 복잡도는 창고 (반복 호출 창고 또는 교체에서 현저하게 사용되는 창고) 와 이전 반복 결과를 저장하는 목록의 크기에 달려 있으며, 창고 안의 원소 개수는 n을 초과하지 않으며, 이전 반복 목록의 원소 개수는 nn이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
