이진 트리를 연결 목록 LeetCode 솔루션으로 병합 라고 말한다 – 주어진 root 이진 트리의 경우 트리를 "연결 목록"으로 병합합니다.
- "연결된 목록"은 같은 것을 사용해야 합니다.
TreeNode클래스right자식 포인터는 목록의 다음 노드를 가리키고left자식 포인터는 항상null. - "연결된 목록"은 다음과 같은 순서여야 합니다. 예약 주문 순회 이진 트리의.
예 1 :
입력:
root = [1,2,5,3,4,null,6]
출력:
[1,null,2,null,3,null,4,null,5,null,6]
예 2 :
입력:
root = []
출력:
[]
예 3 :
입력:
root = [0]
출력:
[0]
알고리즘 –
아이디어 -
- 이진 트리를 평면화하기 위해 먼저 왼쪽 하위 트리의 가장 오른쪽 요소를 찾고 가장 오른쪽 요소를 얻은 후 해당 노드의 오른쪽 포인터를 주어진 트리의 오른쪽 하위 트리와 연결합니다.
- 2단계에서 루트 노드의 오른쪽 포인터를 왼쪽 하위 트리와 연결하고 왼쪽 하위 트리를 null로 설정합니다.
- 3단계에서 루트 노드는 오른쪽 하위 트리 노드입니다. 이 노드에서 동일한 프로세스가 발생하고 모든 왼쪽 부분이 null이 될 때까지 프로세스가 계속 계속됩니다.
연결 목록 Leetcode 솔루션에 이진 트리 평면화 접근 방식 –
– 처음에는 while(root != null) 루프를 실행한 다음 두 개의 변수를 사용하여 왼쪽 하위 트리를 저장합니다.
– 그런 다음 while(k.left != null)을 사용하여 왼쪽 하위 트리의 가장 오른쪽 노드를 확인하고 (k.right = root.right)를 사용하여 해당 노드를 오른쪽 하위 트리와 연결합니다.
– 그런 다음 루트 노드의 오른쪽 포인터를 왼쪽 하위 트리(root.right = left)와 연결하고 루트 노드의 왼쪽 포인터를 null(root.left=null)로 설정하고 ( root = root.right ) 업데이트하므로 이제 루트가 오른쪽입니다. 하위 트리 노드.
– 이 프로세스는 모든 왼쪽 하위 트리 부분이 오른쪽 하위 트리가 될 때까지 계속됩니다. 따라서 이진 트리가 평평해집니다.
파이썬 솔루션:
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
while(root):
if root.left:
k = root.left
temp = root.left
while(k.right):
k = k.right
k.right = root.right
root.right = temp
root.left = None
root = root.right
자바 솔루션:
class Solution {
public void flatten(TreeNode root) {
while (root != null) {
if (root.left != null) {
TreeNode k = root.left;
TreeNode temp = root.left;
while (k.right != null) k = k.right;
k.right = root.right;
root.right = temp;
root.left = null;
}
root = root.right;
}
}
}
시간 복잡도: O(N)
공간 복잡성 : O (1)
한 번만 탐색했으므로 시간 복잡도는 o(n)입니다.
추가 공간을 사용하지 않았으므로 공간 복잡성은 o(1) 일정한 추가 공간이 됩니다.
비슷한 질문 – https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm
