이진 트리 내부 순회

다른 Leetcode 바이너리 트리 챌린지로 분기합니다! 이것은 내가 중위 순회에 대해 처음 배우는 것이기 때문에 그 과정을 이해하게 되어 기뻤습니다! 거의 모든 LeetCode 질문과 마찬가지로 지시 사항은 기만적일 수 있습니다. 이진 트리의 루트가 주어지면 노드 값의 중위 순회를 반환합니다.

저와 같은 이진 트리를 처음 사용하는 경우 inorder가 무엇을 의미하는지 잘못 이해했습니다. inorder traversal의 패턴을 이해하면 이 문제를 해결하는 방법을 알 수 있습니다.

Inorder Traversal은 왼쪽, 루트, 오른쪽 순으로 진행됩니다.

입력을 이해하기 위해 이것을 첫 번째 예에 적용해 보겠습니다.



위의 예에서 노드 1부터 시작합니다. 왼쪽 노드가 없으므로 루트인 1로 돌아갑니다. 그런 다음 노드 2로 오른쪽으로 진행합니다. 왼쪽 루트(예제에서 3) 다음에 오른쪽 루트가 옵니다. 이것은 우리에게 출력 [ 1, 3, 2]을 제공합니다.

이 솔루션의 경우 재귀적으로 해결할 것입니다. 이것은 우리가 기본 케이스와 재귀 케이스를 추적하기를 원한다는 것을 의미합니다. 기본 케이스는 반환할 때/함수를 종료할 때를 의미합니다.

다음은 시작 코드입니다.

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

기본 사례의 경우 루트가 없음이면 함수를 종료합니다. 출력이 목록이므로 빈 목록을 반환하려고 합니다.

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      if root is None:
          return []

루트가 없음이 아니면 중위 순회를 수행합니다. 이것은 우리가 루트에서 시작하여 논의한 패턴을 따르는 inorderTraversal이라는 멋진 내장 함수를 통해 수행됩니다.

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      if root is None:
          return []
      return self.inorderTraversal(root.left) + [root.val]+ self.inorderTraversal(root.right)

우리는 root.left를 인수로 추가합니다. 왜냐하면 그것이 순서가 남아있는 inorder traversal과 정렬되기 때문입니다. 그런 다음 루트 값을 추가합니다(이 경우 노드 1). 그리고 마지막으로 (root.right) 인수를 사용하여 inorderTraversal을 호출합니다. 순서대로 호출하는 마지막 쪽이기 때문입니다.

이 반환 값을 분해하면 왼쪽, 루트, 오른쪽의 순서 패턴을 변환하여 배열로 반환합니다.

결론:
나는 중위 순회에 대해 전혀 몰랐습니다. 나는 그들이 1, 2, 3과 같은 시간적 값으로 순서를 따를 것이라고 생각했지만 완전히 틀렸습니다! inorder traversal의 순서를 모르기 때문에 인터넷에 도움을 요청하기 전에 이 문제를 해결하는 데 방해가 되었습니다. 왜냐하면 내가 공부하는 만큼 항상 새로운 개념이 나올 것이기 때문입니다.