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

Giả sử chúng ta có một cây nhị phân và một danh sách chuỗi moves bao gồm "R" (Right), "L" (Left) và "U" (Up). Bắt đầu từ root, chúng ta phải duyệt cây bằng cách thực hiện từng di chuyển trong moves, trong đó: "R" chỉ duyệt sang con phải. "L" chỉ duyệt sang con trái. "U" chỉ duyệt đến nút cha.

Ví dụ, nếu đầu vào như hình:

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

Để giải quyết, chúng ta thực hiện các bước sau:

• past := danh sách mới
• với mỗi move trong moves:
  • thêm root vào cuối past
  • nếu move là "L", root := left của root
  • ngược lại nếu move là "R", root := right của root
  • ngược lại (move là "U"):
    • xóa phần tử cuối khỏi past
    • root := phần tử cuối của past và xóa nó khỏi past
• trả về giá trị của root

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

Input

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

Output

3