이진 트리를 연결 목록 LeetCode 솔루션으로 병합

이진 트리를 연결 목록 LeetCode 솔루션으로 병합 라고 말한다 – 주어진 root 이진 트리의 경우 트리를 "연결 목록"으로 병합합니다.

  • "연결된 목록"은 같은 것을 사용해야 합니다. TreeNode 클래스 right 자식 포인터는 목록의 다음 노드를 가리키고 left 자식 포인터는 항상 null.
  • "연결된 목록"은 다음과 같은 순서여야 합니다. 예약 주문 순회 이진 트리의.

 

예 1 :

이진 트리를 연결 목록 LeetCode 솔루션으로 병합입력:

 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 ) 업데이트하므로 이제 루트가 오른쪽입니다. 하위 트리 노드.

– 이 프로세스는 모든 왼쪽 하위 트리 부분이 오른쪽 하위 트리가 될 때까지 계속됩니다. 따라서 이진 트리가 평평해집니다.

 

이진 트리를 연결 목록 LeetCode 솔루션으로 병합

이진 트리를 연결 목록 LeetCode 솔루션으로 병합

파이썬 솔루션:

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

이진 트리 Leetcode 솔루션의 가장 낮은 공통 조상

문제 설명 이진 트리의 가장 낮은 공통 조상 LeetCode 솔루션 – "이진 트리의 가장 낮은 공통 조상"은 이진 트리의 루트와 트리의 두 노드를 제공한다고 명시되어 있습니다. 이 두 노드의 가장 낮은 공통 조상을 찾아야 합니다. 최저 공통 …

자세히보기

각 노드 Leetcode 솔루션에 다음 오른쪽 포인터 채우기

문제 설명 각 노드에서 다음 오른쪽 포인터 채우기 LeetCode 솔루션 – "각 노드에서 다음 오른쪽 포인터 채우기"는 완벽한 이진 트리의 루트가 주어지고 노드의 다음 각 포인터를 다음 오른쪽 노드로 채워야 한다고 명시합니다. 다음이 없다면...

자세히보기

노드 삭제 및 Forest Leetcode 솔루션 반환

문제 설명 노드 삭제 및 포리스트 반환 LeetCode 솔루션 – "노드 삭제 및 포리스트 반환"은 각 노드에 고유한 값이 있는 이진 트리의 루트가 주어졌음을 나타냅니다. 우리는 또한 to_delete 배열을 받았는데, 여기서 …

자세히보기

이진 검색 트리 Leetcode 솔루션 복구

문제 설명 이진 검색 트리 복구 LeetCode 솔루션 – "이진 검색 트리 복구"는 이진 검색 트리의 루트가 주어지면 정확히 두 노드의 값이 실수로 바뀌는 경우를 나타냅니다. 구조를 변경하지 않고 트리를 복구해야 합니다. 예: 입력: root = [1,3,null,null,2] 출력: [3,1,null,null,2] …

자세히보기

대칭 트리 Leetcode 솔루션

문제 설명 대칭 트리 LeetCode 솔루션 – "대칭 트리"는 이진 트리의 루트가 주어지고 주어진 이진 트리가 자신의 거울인지(중심을 중심으로 대칭인지) 확인해야 한다고 말합니다. 예이면 true, 그렇지 않으면 false를 반환해야 합니다. 예시: …

자세히보기

이진 트리 Leetcode 솔루션에서 좋은 노드 계산

문제 설명이 문제에서 이진 트리는 루트와 함께 제공됩니다. 루트에서 X까지의 경로에 X보다 큰 값을 가진 노드가 없으면 트리의 노드 X는 good이라는 이름이 지정됩니다. 우리는…에서 좋은 노드의 수를 반환해야합니다.

자세히보기

이진 트리 Leetcode 솔루션의 최대 깊이

문제 설명 문제에서 이진 트리가 주어지고 주어진 트리의 최대 깊이를 찾아야합니다. 이진 트리의 최대 깊이는 루트 노드에서 가장 먼 리프 노드까지 가장 긴 경로를 따라있는 노드 수입니다. 예 3 /…

자세히보기

이진 트리 Leetcode 솔루션의 최소 깊이

이 문제에서 주어진 이진 트리의 루트에서 리프까지의 최단 경로 길이를 찾아야합니다. 여기서 "경로 길이"는 루트 노드에서 리프 노드까지의 노드 수를 의미합니다. 이 길이를 최소라고합니다.

자세히보기

Translate »