Python에서 이진 트리의 Inorder Traversal을 수행하는 프로그램

이진 트리가 있다고 가정합니다. root의 inorder traversal을 목록으로 포함하는 목록을 찾아야 합니다. 우리가 알다시피 중위 순회는 다음과 같은 트리의 모든 노드를 순회하는 방법입니다.

• 왼쪽 하위 트리를 재귀적으로 순회합니다.

• 현재 노드를 탐색합니다.

• 오른쪽 하위 트리를 재귀적으로 순회합니다.

우리는 이 문제를 반복적인 방식으로 해결하려고 노력해야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은 [12,13,4,16,7,14,22]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• inorder :=새 목록

• 스택 :=빈 스택

• 다음을 무한히 수행하십시오.

  • 루트가 null이 아니면

    • 스택에 루트 푸시

    • root :=root의 왼쪽

  • 그렇지 않으면 스택이 비어 있지 않으면

    • root :=스택의 최상위 요소 및 스택에서 팝

    • inorder의 끝에 root 값 삽입

    • root :=root의 오른쪽

  • 그렇지 않으면

    • 루프에서 나오다

• 순서대로 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None
class Solution:
   def solve(self, root):
      inorder = []
      stack = []
      while True:
         if root:
            stack.append(root)
            root = root.left
         elif stack:
            root = stack.pop()
            inorder.append(root.val)
            root = root.right
         else:
            break
      return inorder

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)

출력

[12, 13, 4, 16, 7, 14, 22]