이진 트리가 있다고 가정합니다. 가장 깊은 노드의 값을 찾아야 합니다. 가장 깊은 노드가 두 개 이상 있으면 가장 왼쪽에 있는 가장 깊은 노드를 반환합니다.
따라서 입력이 다음과 같으면
4와 7이 가장 깊지만 4가 가장 많이 남으므로 출력은 4가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
queue :=하나의 노드 루트가 있는 큐입니다.
-
left_max :=루트 값
-
대기열 크기> 0 동안 수행
-
level_size :=큐의 크기
-
범위 0에서 level_size까지의 i에 대해 수행
-
temp :=대기열의 첫 번째 요소 및 삭제
-
i가 0과 같으면
-
left_max :=온도 값
-
-
temp의 왼쪽이 0이 아닌 경우
-
대기열 끝에 임시 왼쪽 삽입
-
-
임시 권한이 null이 아니면
-
대기열의 끝에 temp의 오른쪽 삽입
-
-
-
left_max 반환
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class TreeNode: def __init__(self, value): self.val = value self.left = None self.right = None class Solution: def solve(self, root): queue = [root] left_max = root.val while len(queue) > 0: level_size = len(queue) for i in range(level_size): temp = queue.pop(0) if i == 0: left_max = temp.val if temp.left: queue.append(temp.left) if temp.right: queue.append(temp.right) return left_max ob = Solution() root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7) print(ob.solve(root))
입력
root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)
출력
4