Chương trình tìm nút sâu nhất bên trái nhất trên cây trong Python

Cho cây nhị phân, tìm giá trị của nút sâu nhất. Nếu có nhiều nút cùng độ sâu, trả về nút bên trái nhất.

Ví dụ: cây như hình → kết quả 4 (4 và 7 cùng sâu, 4 bên trái).

Giải thuật (BFS - Duyệt cấp độ)

1. Khởi tạo hàng đợi queue = [root], left_max = root.val.
2. Khi hàng đợi không rỗng:
   • level_size = len(queue).
   • Duyệt i từ 0 đến :
     • Lấy temp = queue.pop(0).
     • Nếu : left_max = temp.val (nút đầu tiên của cấp = trái nhất).
     • Thêm con trái, con phải vào hàng đợi nếu có.
3. Trả về (sau vòng lặp cuối cùng, đây là nút trái nhất của cấp sâu nhất).

Ví dụ minh họa

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

class Solution:
    def solve(self, root):
        queue = [root]
        left_max = root.val
        while len(queue) > 0:
            level_size = len(queue)
            for i in range(level_size):
                temp = queue.pop(0)
                if i == 0:
                    left_max = temp.val
                if temp.left:
                    queue.append(temp.left)
                if temp.right:
                    queue.append(temp.right)
        return left_max

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))  # Output: 4

Đầu vào

root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)

Đầu ra

4