Python3의 이진 트리 사전 주문 순회에 대한 반복 솔루션

이진 트리는 각 상위 노드에 최대 2개의 하위 노드가 있는 계층적 데이터 구조입니다. 오늘의 기사에서는 많은 기술 코딩 인터뷰에서 나타나는 중요한 주제를 살펴보겠습니다.

문제 설명: 이진 트리의 루트가 주어지면 해당 노드 값의 사전 순회를 반환합니다. 재귀적 솔루션 대신 반복적 솔루션을 제공하십시오.

해결책:

이진 트리에서 선주문 순회는 다음 순서로 발생합니다.

먼저 루트를 방문하십시오

왼쪽 하위 트리 탐색

오른쪽 하위 트리 탐색

반복적인 솔루션으로 이 문제를 해결하려면 스택 데이터 구조를 구현해야 합니다. 연산이 LIFO(Last In First Out) 순서로 수행되는 비선형 데이터 구조입니다. 답변에 대한 접근 방식은 간단하며 다음과 같습니다.

두 목록을 초기화합니다. 하나는 출력을 전달하고 다른 하나는 스택 데이터 구조로 작동합니다. 스택은 이진 트리의 루트 값으로 초기화됩니다.

그런 다음 값이 있는 동안 스택에서 while 루프를 수행합니다. 루프에서 다음 작업이 순서대로 수행됩니다.

스택에서 최상위 값(루트 노드)을 제거(팝)하고 출력 목록에 추가합니다

.

팝된 값의 오른쪽 자식을 스택으로 푸시합니다

.

팝된 값의 왼쪽 자식을 스택으로 푸시합니다

.

루프 끝에서 출력 목록을 반환합니다

.

이 프로세스의 결과 루트 값이 먼저 액세스되고 왼쪽 하위 트리가 그 다음 오른쪽 하위 트리 값이 마지막으로 액세스됩니다.

오른쪽 자식이 먼저 스택에 들어간 다음 왼쪽 자식이 스택에 푸시된다는 점에 유의하는 것이 중요합니다. 이는 스택의 LIFO 특성 때문입니다. 이렇게 하면 오른쪽 자식보다 먼저 왼쪽 자식에 액세스할 수 있습니다.

TALK는 저렴합니다. 코드를 보여주세요:

# Definition of a Binary Tree node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        output, nodestack = [], [root]
        while nodestack:
            node = nodestack.pop()
            if node:  # preorder: root -> left -> right
                output.append(node.val)
                nodestack.append(node.right)
                nodestack.append(node.left)
        return output

이 글이 도움이 되었다면 Python에서 더 많은 DSA 콘텐츠를 보려면 내 뉴스레터를 좋아하고 구독하십시오.