크기가 n인 정렬된 연결 목록 노드가 있다고 가정하고 k =floor of (n / 2)의 가장 작은 값을 루트로 설정하여 이진 검색 트리를 만들어야 합니다. 그런 다음 k번째 노드의 왼쪽 연결 목록을 사용하여 왼쪽 하위 트리를 재귀적으로 구성합니다. 그리고 k번째 노드의 우측 연결 리스트를 이용하여 우측 서브트리를 재귀적으로 구성한다.
따라서 입력이 [2,4,5,7,10,15]와 같으면 출력은
이 문제를 해결하기 위해 다음 단계를 따르겠습니다-
-
solve() 메서드를 정의하면 노드가 필요합니다.
-
노드가 null이면
-
null 반환
-
-
다음 노드가 null이면
-
노드 값을 가진 새 트리 노드를 반환
-
-
느린 :=노드, 빠른 :=노드
-
이전 :=없음
-
fast와 fast의 다음이 null이 아닌 동안 수행
-
이전 :=느림
-
느린 :=느린 다음
-
fast :=빠른 다음의 다음
-
-
이전의 다음 :=없음
-
root :=값이 느린 새 트리 노드
-
루트 왼쪽 :=해결(노드)
-
루트 오른쪽 :=해결(느림의 다음)
-
루트 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class ListNode: def __init__(self, data, next = None): self.val = data self.next = next class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def make_list(elements): head = ListNode(elements[0]) for element in elements[1:]: ptr = head while ptr.next: ptr = ptr.next ptr.next = ListNode(element) return head def print_tree(root): if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) class Solution: def solve(self, node): if not node: return None if not node.next: return TreeNode(node.val) slow = fast = node prev = None while fast and fast.next: prev = slow slow = slow.next fast = fast.next.next prev.next = None root = TreeNode(slow.val) root.left = self.solve(node) root.right = self.solve(slow.next) return root ob = Solution() head = make_list([2,4,5,7,10,15]) root = ob.solve(head) print_tree(root)
입력
[2,4,5,7,10,15]
출력
2, 4, 5, 7, 10, 15,