리프 수에 대한 루트 합계 LeetCode 솔루션

문제 진술 합 루트에서 리프 숫자까지 LeetCode 솔루션은 다음과 같이 말합니다. – 0에서 9까지의 숫자만 포함하는 이진 트리의 루트가 제공됩니다. 트리의 각 루트에서 리프 경로는 숫자를 나타냅니다. 예를 들어, 루트에서 리프 경로 1 -> 2 -> 3은 숫자 123을 나타냅니다. 모든 루트에서 리프 숫자의 총합을 반환합니다. 테스트 …

자세히보기

이진 트리 중위 순회 LeetCode 솔루션

문제 설명: 이진 트리 중위 순회 LeetCode 솔루션 이진 트리의 루트가 주어지면 해당 노드 값의 중위 순회를 반환합니다. 예 1: 입력: root = [1,null,2,3] 출력: [1,3,2] 예 2: 입력: root = [] 출력: [] 예 3: 입력: root = [1] 출력: [1] 제약 조건: 노드의 수 …

자세히보기

이진 트리를 연결 목록 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 Solutions

이진 트리와 정수 K가 제공됩니다. 우리의 목표는 트리에 루트-투-리프 경로가 있는지 여부를 반환하여 합계가 target-K와 동일하도록하는 것입니다. 경로의 합은 경로에있는 모든 노드의 합입니다. 2 / \…

자세히보기

Translate »