Kiểm tra duyệt lá của hai cây nhị phân có giống nhau không (Python)

Bài toán: Cho hai cây nhị phân, kiểm tra chuỗi các nút lá (leaf nodes) duyệt từ trái sang có giống nhau hay không.

Cấu trúc TreeNode

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = self.right = None
    
    def is_leaf(self):
        return self.left is None and self.right is None

Thuật toán DFS lặp với stack

def solve(r1, r2):
    s1, s2 = [r1], [r2]
    
    while s1 or s2:
        if not s1 or not s2:
            return False
        
        # Tìm lá tiếp theo của cây 1
        node1 = s1.pop()
        while node1 and not node1.is_leaf():
            if node1.right: s1.append(node1.right)
            if node1.left: s1.append(node1.left)
            node1 = s1.pop()
        
        # Tìm lá tiếp theo của cây 2
        node2 = s2.pop()
        while node2 and not node2.is_leaf():
            if node2.right: s2.append(node2.right)
            if node2.left: s2.append(node2.left)
            node2 = s2.pop()
        
        # So sánh
        if (node1 is None) != (node2 is None):
            return False
        if node1 and node2 and node1.val != node2.val:
            return False
    
    return True

Test

# Cây 1:     2          Cây 2:     1
#           / \                   / \
#          3   4                 6   9
#         /   / \               /   / \
#        5   7   8             5   7   8
# Lá cả hai: [5, 7, 8] → True

Kết quả

True

Giải thích

• Duyệt DFS pre-order (root-left-right) nhưng dùng stack: push right trước, left sau → pop ra left trước.
• Mỗi lần pop, nếu không phải lá thì push con cái, tiếp tục pop cho đến khi gặp lá.
• So sánh giá trị lá tương ứng của hai cây.
• Độ phức tạp: O(N) time, O(H) space (H = height).