Python에서 교대로 이진 트리 수준을 순회하는 프로그램

이진 트리가 있다고 가정하고 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 교대로 각 레벨의 값을 표시해야 합니다.

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

그러면 출력은 [5, -10, 4, -2, -7, 15]

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

• 루트가 null이면

  • 새 목록 반환

• s1 :=처음에 루트를 삽입하는 목록

• s2 :=새 목록

• res :=새 목록

• s1이 비어 있지 않거나 s2가 비어 있지 않은 동안 수행

  • s1이 비어 있지 않은 동안 수행

    • node :=s1에서 마지막 요소 삭제

    • 노드의 왼쪽이 null이 아니면

      • s2의 끝에서 노드의 왼쪽에 삽입

    • 노드의 오른쪽이 null이 아니면

      • s2의 끝에서 노드의 오른쪽에 삽입

    • res

      끝에 노드 값 삽입

  • s2가 비어 있지 않은 동안 수행

    • node :=s2에서 마지막 요소 삭제

    • 노드의 오른쪽이 null이 아니면

      • s1의 끝에 노드의 오른쪽 삽입

    • 노드의 왼쪽이 비어 있지 않으면

      • s1의 끝에 노드의 왼쪽 삽입

    • res

      끝에 노드 값 삽입

• 반환 해상도

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

예시

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      if not root:
         return []
      s1 = [root]
      s2 = []
      res = []
      while s1 or s2:
         while s1:
            node = s1.pop()
            if node.left:
               s2.append(node.left)
            if node.right:
               s2.append(node.right)
            res.append(node.val)
         while s2:
            node = s2.pop()
            if node.right:
               s1.append(node.right)
            if node.left:
               s1.append(node.left)
            res.append(node.val)
      return res

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(-10)
root.left.left = TreeNode(-2)
root.right.left = TreeNode(-7)
root.right.right = TreeNode(15)
print(ob.solve(root))

입력

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(-10)
root.left.left = TreeNode(-2)
root.right.left = TreeNode(-7)
root.right.right = TreeNode(15)

출력

[5, -10, 4, -2, -7, 15]