Chương trình duyệt cây nhị phân bằng cách sử dụng danh sách các hướng trong Python

Giả sử chúng ta có một cây nhị phân và danh sách các chuỗi di chuyển bao gồm "R" (Phải), "L" (Trái) và "U" (Lên). Bắt đầu từ gốc, chúng ta phải đi ngang qua cây bằng cách thực hiện từng bước di chuyển trong đó:"R" cho biết đi ngang đến cây con bên phải. "L" cho biết đi qua phần con bên trái. "U" cho biết đi ngang tới gốc của nó.

Vì vậy, nếu đầu vào giống như

["R", "R", "U", "L"], thì đầu ra sẽ là 3

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• quá khứ:=một danh sách mới

• đối với mỗi bước di chuyển, hãy thực hiện

  • chèn root vào cuối quá khứ

  • nếu di chuyển giống như "L", thì

    • root:=left of root

  • ngược lại khi di chuyển giống như "R" thì

    • root:=right of root

  • nếu không,

    • xóa phần tử cuối cùng khỏi quá khứ

    • root:=phần tử cuối cùng từ quá khứ và xóa nó khỏi quá khứ

• giá trị trả về của root

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

3