Python에서 방향 목록을 사용하여 이진 트리를 탐색하는 프로그램

<시간/>

이진 트리와 "R"(오른쪽), "L"(왼쪽) 및 "U"(위쪽)로 구성된 문자열 이동 목록이 있다고 가정합니다. 루트에서 시작하여 이동에서 각 이동을 수행하여 트리를 순회해야 합니다. 여기서 "R"은 오른쪽 자식으로의 순회를 나타냅니다. "L"은 왼쪽 자식으로의 트래버스를 나타냅니다. "U"는 상위 항목으로의 트래버스를 나타냅니다.

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

["R","R","U","L"]이면 출력은 3

이 됩니다.

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

과거 :=새 목록
동작의 각 동작에 대해 수행
- 과거의 끝에 루트 삽입
- 이동이 "L"과 같으면
  - root :=root의 왼쪽
- 그렇지 않으면 이동이 "R"과 같을 때
  - root :=root의 오른쪽
- 그렇지 않으면
  - 과거에서 마지막 요소 삭제
  - root :=과거의 마지막 요소 및 과거에서 삭제
루트의 반환 값

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

예

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, moves):
      past = []
      for move in moves:
         past.append(root)
         if move == "L":
            root = root.left
         elif move == "R":
            root = root.right
         else:
            past.pop()
            root = past.pop()
      return root.val
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
traverse = ["R","R","U","L"]
print(ob.solve(root, traverse))

입력

root = TreeNode(2) root.right = TreeNode(4) root.right.left =
TreeNode(3) root.right.right = TreeNode(5) ["R","R","U","L"]