Chương trình kiểm tra chuỗi lá của hai cây nhị phân có giống nhau không bằng Python

Cho hai cây nhị phân. Kiểm tra chuỗi giá trị các lá (duyệt inorder từ trái sang phải) của hai cây có giống nhau hay không.

Ví dụ: hai cây cho trước → True (chuỗi lá đều là [2,6]).

Giải thuật

• Hàm inorder(root, c) duyệt inorder, thu thập giá trị lá vào danh sách c.
• So sánh hai danh sách lá của hai cây.

Ví dụ minh họa

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

class Solution:
    c = []
    def inorder(self, root, c=None):
        if c is None:
            c = []
        if root:
            self.inorder(root.left, c)
            if not root.left and not root.right:
                c.append(root.val)
            self.inorder(root.right, c)
        return c
    def solve(self, root0, root1):
        if self.inorder(root0) == self.inorder(root1):
            return True
        else:
            return False

ob = Solution()
root1 = TreeNode(1)
root1.right = TreeNode(3)
root1.right.left = TreeNode(2)
root1.right.right = TreeNode(6)
root2 = TreeNode(1)
root2.left = TreeNode(3)
root2.right = TreeNode(6)
root2.left.left = TreeNode(2)
print(ob.solve(root1, root2))

Đầu vào

root1 = TreeNode(1) ... root2 = TreeNode(1) ...

Đầu ra

True