Chương trình tìm nút sâu thứ hai trong cây nhị phân bằng Python

Cho cây nhị phân. Tìm độ sâu của lá sâu thứ hai. Nếu có nhiều lá sâu nhất, lá sâu thứ hai là lá kế tiếp. Gốc độ sâu 0.

Ví dụ: cây minh họa → 1 (lá sâu thứ hai là nút 3).

Giải thuật

• BFS theo cấp độ (level order).
• Biến count (độ sâu hiện tại), prev (độ sâu lá trước), now (độ sâu lá hiện tại).
• Khi gặp lá đầu tiên tại cấp độ mới: prev = now, now = count.
• Sau BFS, trả về prev.

Ví dụ minh họa

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

class Solution:
    def solve(self, root):
        if root is None:
            return None
        nodes = [root]
        count = 0
        prev = 0
        now = 0
        while nodes:
            new = []
            flag = True
            for node in nodes:
                if flag and (not node.left) and (not node.right):
                    prev = now
                    now = count
                    flag = False
                if node.left:
                    new.append(node.left)
                if node.right:
                    new.append(node.right)
            nodes = new
            count += 1
        return prev

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)
print(ob.solve(root))

Đầu vào

root = TreeNode(2) ...

Đầu ra

1